Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Divisors in residue classes

Author: H. W. Lenstra
Journal: Math. Comp. 42 (1984), 331-340
MSC: Primary 11Y05; Secondary 11A51, 11N69
MathSciNet review: 726007
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper the following result is proved. Let r, s and n be integers satisfying $ 0 \leqslant r < s < n$, $ s > {n^{1/3}}$, $ \gcd (r,s) = 1$. Then there exist at most 11 positive divisors of n that are congruent to r modulo s. Moreover, there exists an efficient algorithm for determining all these divisors. The bound 11 is obtained by means of a combinatorial model related to coding theory. It is not known whether 11 is best possible; in any case it cannot be replaced by 5. Nor is it known whether similar results are true for significantly smaller values of $ \log s/\log n$. The algorithm treated in the paper has applications in computational number theory.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11A51, 11N69

Retrieve articles in all journals with MSC: 11Y05, 11A51, 11N69

Additional Information

Keywords: Divisors, residue classes, coding theory, computational number theory
Article copyright: © Copyright 1984 American Mathematical Society