Number Theory   Proof that Wagstaff Prime Numbers are Infinite

Authors: Stephen Marshall

The Wagstaff prime is a prime number q of the form: q = (2^p- 1)/3 where, p is an odd prime. Wagstaff primes are named after the mathematician Samuel S. Wagstaff Jr. Wagstaff primes appear in the New Mersenne conjecture and have applications in cryptography. The New Mersenne conjecture (Bateman et al. 1989) states that for any odd natural number p, if any two of the following conditions hold, then so does the third: 1. p = 2k ± 1 or p = 4k ± 3 for some natural number k. 2. 2p − 1 is prime (a Mersenne prime). 3. (2p + 1) / 3 is prime (a Wagstaff prime). There is no simple primality test analogous to the Lucas-Lehmer test for Wagstaff primes, so all recent primality proofs of Wagstaff primes have used elliptic curve primality proving which is very time consuming. A Wagstaff prime can also be interpreted as a repunit prime of base , as if p is odd, as it must be for the above number to be prime. The first three Wagstaff primes are 3, 11, and 43 because The first few Wagstaff primes are: 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … (sequence A000979 in the OEIS) As of October 2014, known exponents which produce Wagstaff primes or probable primes are: 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, (all known Wagstaff primes) 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 (Wagstaff probable primes) (sequence A000978 in the OEIS) In February 2010, Tony Reix discovered the Wagstaff probable prime: which has 1,213,572 digits and was the 3rd biggest probable prime ever found at this date. In September 2013, Ryan Propper announced the discovery of two additional Wagstaff probable primes: and, Each is a probable prime with slightly more than 4 million decimal digits. It is not currently known whether there are any exponents between 4031399 and 13347311 that produce Wagstaff probable primes. Note that when p is a Wagstaff prime, need not to be prime, the first counterexample is p = 683, and it is conjectured that if p is a Wagstaff prime and p>43, then is composite.