New primality criteria and factorizations of

Authors:
John Brillhart, D. H. Lehmer and J. L. Selfridge

Journal:
Math. Comp. **29** (1975), 620-647

MSC:
Primary 10A25

DOI:
https://doi.org/10.1090/S0025-5718-1975-0384673-1

Erratum:
Math. Comp. **39** (1982), 747-757.

Erratum:
Math. Comp. **39** (1982), 747.

MathSciNet review:
0384673

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A collection of theorems is developed for testing a given integer *N* for primality. The first type of theorem considered is based on the converse of Fermat's theorem and uses factors of . The second type is based on divisibility properties of Lucas sequences and uses factors of . The third type uses factors of both and and provides a more effective, yet more complicated, primality test. The search bound for factors of and properties of the hyperbola are utilized in the theory for the first time.

A collection of 133 new complete factorizations of and associated numbers is included, along with two status lists: one for the complete factorizations of ; the other for the original Mersenne numbers.

**[1]**M. BEELER, R. W. GOSPER & R. SCHROEPPEL,*Artificial Intelligence Memo*239, MIT, Artificial Intelligence Laboratory, 1972, p. 13.**[2]**J. BRILLHART, "Concerning the numbers prime,"*Math. Comp.*, v. 16, 1962, pp. 424-430. MR**26**#6100. MR**0148593 (26:6100)****[3]**J. BRILLHART, "Some miscellaneous factorizations,"*Math. Comp.*, v. 17, 1963, pp. 447-450.**[4]**J. BRILLHART & J. L. SELFRIDGE, "Some factorizations of and related results,"*Math Comp.*, v. 21, 1967, pp. 87-96; Corrigendum,*ibid.*, p. 751. MR**37**#131. MR**0224532 (37:131)****[5]**M. KRAITCHIK,*Théorie des Nombres*, vol. 2, Gauthier-Villars, Paris, 1926, p. 135.**[6]**D. H. LEHMER, "Tests for primality by the converse of Fermat's theorem,"*Bull. Amer. Math. Soc.*, v. 33, 1927, pp. 327-340. MR**1561374****[7]**D. H. LEHMER, "An extended theory of Lucas functions,"*Ann. of Math.*, v. 31, 1930, pp. 419-448. MR**1502953****[8]**D. H. LEHMER, "Computer technology applied to the theory of numbers,"*Studies in Number Theory*, MAA Studies in Math., vol. 6, Prentice-Hall, Englewood Cliffs, N. J., 1969, pp. 117-151. MR**40**#84. MR**0246815 (40:84)****[9]**E. LUCAS, "Considerations nouvelles sur la théorie des nombres premiers et sur la division géométrique de la circonference en parties égales,"*Assoc. Franç. Avancement Sci. C. R.*, v. 6, 1877, p. 162.**[10]**E. LUCAS, "Théorie des fonctions numériques simplement périodiques,"*Amer. J. Math.*, v. 1, 1878, pp. 184-240, 289-321. MR**1505176****[11]**E. LUCAS, "*Théorie des nombres*, Tome I:*Le Calcul des Nombres Entiers, le Calcul des Nombres Rationnels, la Divisibilité Arithmétique*, Librairie Scientifique et Technique, Albert Blanchard, Paris, 1961, pp. 423, 441. MR**23**#A828. MR**0123503 (23:A828)****[12]**M. A. MORRISON, "A note on primality testing using Lucas sequences,"*Math. Comp.*, v. 29, 1975, pp. 181-182. MR**0369234 (51:5469)****[13]**M. A. MORRISON & J. BRILLHART, "A method of factoring and the factorization of ,"*Math. Comp.*, v. 29, 1975, pp. 183-205. MR**0371800 (51:8017)****[14]**H. C. POCKLINGTON, "The determination of the prime or composite nature of large numbers by Fermat's theorem,"*Proc. Cambridge Philos. Soc.*, v. 18, 1914-16, pp. 29-30.**[15]**E. PROTH, "Théorèmes sur les nombres premiers,"*C.R. Acad. Sci. Paris*, v. 87, 1878, p. 926.**[16]**H. RIESEL,*En Book om Primtal*, Studentlitteratur, Lund, Sweden, 1968, pp. 44-65. MR**42**#4507. MR**0269612 (42:4507)****[17]**H. RIESEL, "Lucasian criteria for the primality of ,"*Math. Comp.*, v. 23, 1969, pp. 869-875. MR**41**#6773. MR**0262163 (41:6773)****[18]**R. M. ROBINSON, "The converse of Fermat's theorem,"*Amer. Math. Monthly*, v. 64, 1957, pp. 703-710. MR**20**#4520. MR**0098057 (20:4520)****[19]**R. M. ROBINSON, "Some factorizations of numbers of the form ,"*MTAC*, v. 11, 1957, pp. 265-268. MR**20**#832. MR**0094313 (20:832)****[20]**J. L. SELFRIDGE & R. K. GUY,*Primality Testing with Applications to Small Machines*, Research Paper #121, Dept. of Math., Univ. of Calgary, Canada, 1971. MR**0319866 (47:8407)****[21]**H. C. WILLIAMS & C. R. ZARNKE, "A report on prime numbers of the forms and ,"*Math. Comp.*, v. 22, 1968, pp. 420-422. MR**37**#2680. MR**0227095 (37:2680)**

Retrieve articles in *Mathematics of Computation*
with MSC:
10A25

Retrieve articles in all journals with MSC: 10A25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1975-0384673-1

Keywords:
Primality testing,
factorization of ,
Lucas sequences,
converse of Fermat's theorem

Article copyright:
© Copyright 1975
American Mathematical Society