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