Divisors in residue classes

Author:
H. W. Lenstra

Journal:
Math. Comp. **42** (1984), 331-340

MSC:
Primary 11Y05; Secondary 11A51, 11N69

DOI:
https://doi.org/10.1090/S0025-5718-1984-0726007-1

MathSciNet review:
726007

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper the following result is proved. Let *r*, *s* and *n* be integers satisfying , , . 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 . The algorithm treated in the paper has applications in computational number theory.

**[1]**H. Alt,*Square rooting is as difficult as multiplication*, Computing**21**(1978/79), no. 3, 221–232 (English, with German summary). MR**620210**, https://doi.org/10.1007/BF02253055**[2]**John Brillhart, D. H. Lehmer, and J. L. Selfridge,*New primality criteria and factorizations of 2^{𝑚}±1*, Math. Comp.**29**(1975), 620–647. MR**0384673**, https://doi.org/10.1090/S0025-5718-1975-0384673-1**[3]**H. Cohen and H. W. Lenstra Jr.,*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, https://doi.org/10.1090/S0025-5718-1984-0726006-X**[4]**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR**568909****[5]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[6]**R. Sherman Lehman,*Factoring large integers*, Math. Comp.**28**(1974), 637–646. MR**0340163**, https://doi.org/10.1090/S0025-5718-1974-0340163-2**[7]**H. W. Lenstra Jr. and R. Tijdeman (eds.),*Computational methods in number theory. Part I*, Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982. MR**700254****[8]**F. J. MacWilliams & N. J. A. Sloane,*The Theory of Error-Correcting Codes*, North-Holland, Amsterdam, 1978.**[9]**R. Y. Pinter,*Using Hyperbolic Tangents in Integer Factoring*, thesis, M.I.T., Cambridge, Mass., 1980.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0726007-1

Keywords:
Divisors,
residue classes,
coding theory,
computational number theory

Article copyright:
© Copyright 1984
American Mathematical Society