## New primality criteria and factorizations of $2^{m}\pm 1$

HTML articles powered by AMS MathViewer

- by John Brillhart, D. H. Lehmer and J. L. Selfridge PDF
- Math. Comp.
**29**(1975), 620-647 Request permission

Erratum: Math. Comp.

**39**(1982), 747-757.

Erratum: Math. Comp.

**39**(1982), 747.

## 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 $N - 1$. The second type is based on divisibility properties of Lucas sequences and uses factors of $N + 1$. The third type uses factors of both $N - 1$ and $N + 1$ and provides a more effective, yet more complicated, primality test. The search bound for factors of $N \pm 1$ and properties of the hyperbola $N = {x^2} - {y^2}$ are utilized in the theory for the first time. A collection of 133 new complete factorizations of ${2^m} \pm 1$ and associated numbers is included, along with two status lists: one for the complete factorizations of ${2^m} \pm 1$; the other for the original Mersenne numbers.

## References

- M. BEELER, R. W. GOSPER & R. SCHROEPPEL,
- John Brillhart,
*Concerning the numbers $2^{2p}+1$, $p$ prime*, Math. Comp.**16**(1962), 424–430. MR**148593**, DOI 10.1090/S0025-5718-1962-0148593-0
J. BRILLHART, "Some miscellaneous factorizations," - John Brillhart and J. L. Selfridge,
*Some factorizations of $2^{n}\pm 1$ and related results*, Math. Comp. 21 (1967), 87-96; corrigendum, ibid.**21**(1967), 751. MR**0224532**, DOI 10.1090/S0025-5718-1967-0224532-3
M. KRAITCHIK, - D. H. Lehmer,
*Tests for primality by the converse of Fermat’s theorem*, Bull. Amer. Math. Soc.**33**(1927), no. 3, 327–340. MR**1561374**, DOI 10.1090/S0002-9904-1927-04368-3 - D. H. Lehmer,
*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, DOI 10.2307/1968235 - D. H. Lehmer,
*Computer technology applied to the theory of numbers*, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR**0246815**
E. LUCAS, "Considerations nouvelles sur la théorie des nombres premiers et sur la division géométrique de la circonference en parties égales," - Edouard Lucas,
*Theorie des Fonctions Numeriques Simplement Periodiques*, Amer. J. Math.**1**(1878), no. 4, 289–321 (French). MR**1505176**, DOI 10.2307/2369373 - Edouard 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 (French). Nouveau tirage augmenté dun avant-propos de Georges Bouligand. MR**0123503** - Michael A. Morrison,
*A note on primality testing using Lucas sequences*, Math. Comp.**29**(1975), 181–182. MR**369234**, DOI 10.1090/S0025-5718-1975-0369234-2 - Michael A. Morrison and John Brillhart,
*A method of factoring and the factorization of $F_{7}$*, Math. Comp.**29**(1975), 183–205. MR**371800**, DOI 10.1090/S0025-5718-1975-0371800-5
H. C. POCKLINGTON, "The determination of the prime or composite nature of large numbers by Fermat’s theorem," - Hans Riesel,
*En bok om primtal*, Studentlitteratur, Lund, 1968 (Swedish). MR**0269612** - Hans Riesel,
*Lucasian criteria for the primality of $N=h\cdot 2^{n} -1$*, Math. Comp.**23**(1969), 869–875. MR**262163**, DOI 10.1090/S0025-5718-1969-0262163-1 - Raphael M. Robinson,
*The converse of Fermat’s theorem*, Amer. Math. Monthly**64**(1957), 703–710. MR**98057**, DOI 10.2307/2309747 - Raphael M. Robinson,
*Some factorizations of numbers of the form $2^{n}\pm 1$*, Math. Tables Aids Comput.**11**(1957), 265–268. MR**94313**, DOI 10.1090/S0025-5718-1957-0094313-6 - J. L. Selfridge and Richard K. Guy,
*Primality testing with application to small machines*, Proceedings of the Washington State University Conference on Number Theory (Washington State Univ., Pullman, Wash., 1971) Dept. Math., Washington State Univ., Pullman, Wash., 1971, pp. 45–51. MR**0319866** - H. C. Williams and C. R. Zarnke,
*A report on prime numbers of the forms $M=(6a+1)2^{2m-1}-1$ and $M^{\prime } =(6a-1)2^{2m}-1$*, Math. Comp.**22**(1968), 420–422. MR**227095**, DOI 10.1090/S0025-5718-1968-0227095-2

*Artificial Intelligence Memo*239, MIT, Artificial Intelligence Laboratory, 1972, p. 13.

*Math. Comp.*, v. 17, 1963, pp. 447-450.

*Théorie des Nombres*, vol. 2, Gauthier-Villars, Paris, 1926, p. 135.

*Assoc. Franç. Avancement Sci. C. R.*, v. 6, 1877, p. 162.

*Proc. Cambridge Philos. Soc.*, v. 18, 1914-16, pp. 29-30. E. PROTH, "Théorèmes sur les nombres premiers,"

*C.R. Acad. Sci. Paris*, v. 87, 1878, p. 926.

## Additional Information

- © Copyright 1975 American Mathematical Society
- Journal: Math. Comp.
**29**(1975), 620-647 - MSC: Primary 10A25
- DOI: https://doi.org/10.1090/S0025-5718-1975-0384673-1
- MathSciNet review: 0384673