Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1984-0726007-1
PII: S 0025-5718(1984)0726007-1
Keywords: Divisors, residue classes, coding theory, computational number theory
Article copyright: © Copyright 1984 American Mathematical Society