Probable prime tests for generalized Mersenne numbers (Q1959045)

The present paper studies the primality of the two families of numbers \(N(p,b)=\frac{b^p+1}{b+1}\) and \(M(p,a)=\frac{a^p-1}{a-1}\),\, where \(b\geq 2\)\, and \(a\geq 3\)\, are integers and \(p\)\, is an odd prime. The approach is similar to the used in the test of Lucas-Lehmer (as well as tests for other families of numbers, tests due to other authors, see [\textit{H. C. Williams}, Édourd Lucas and primality testing. Canadian Mathematical Society Series of Monographs and Advanced Texts 22. New York, NY: John Wiley (1998; Zbl 1155.11363)]): starting from the roots of a quadratic equation they are defined two sequences of integers and a recurring sequence \(\{S_i\}\). Then a relationship is deduced among the primality of the number candidate of the corresponding family and the term \(S_{p-1}\) of the recurring sequence. Sections 2 and 3 study the case \(N(p,b)=\frac{b^p+1}{b+1}\) (for even and odd \(b\), respectively) and Section 4 deals with the case \(M(p,a)=\frac{a^p-1}{a-1}\). The obtained results (Theorems 2.8, 3.7, 4.2 and 4.4) show the relationships that \(S_{p-1}\) should verify, \textit{assuming the candidate's primality}. Then the previous results provide compositeness tests (if the candidate doesn't verify the relation it is certainly composite). However Sections 5 and 6 apply these results to the design of primality tests and to the detection of eventual false positives. The numerical results are collected in Table 1 (for \(b =3,5,6,7,9,10,11\) and 12) and Table 2 (for \(a= 3,5,6,7,10,11\) and 12). The tests do not produce false positives and in the author's words ``we have made no progress in proving that any of our tests are deterministic, and so there remains this possibility''.