Wagstaff prime

In number theory, a Wagstaff prime is a prime number of the form

${\displaystyle {{2^{p}+1} \over 3}}${\displaystyle {{2^{p}+1} \over 3}}

where p is an odd prime. Wagstaff primes are named after the mathematician Samuel S. Wagstaff Jr.; the prime pages credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes appear in the New Mersenne conjecture and have applications in cryptography.

The first three Wagstaff primes are 3, 11, and 43 because

${\displaystyle {\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}}${\displaystyle {\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}}

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... (sequence A000979 in the OEIS)

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, ... (sequence A000978 in the OEIS)

It is natural to consider^[2] more generally numbers of the form

${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}

where the base ${\displaystyle b\geq 2}${\displaystyle b\geq 2}. Since for ${\displaystyle n}${\displaystyle n} odd we have

${\displaystyle {\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)}${\displaystyle {\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)}

these numbers are called "Wagstaff numbers base ${\displaystyle b}${\displaystyle b}", and sometimes considered^[3] a case of the repunit numbers with negative base ${\displaystyle -b}${\displaystyle -b}.

For some specific values of ${\displaystyle b}${\displaystyle b}, all ${\displaystyle Q(b,n)}${\displaystyle Q(b,n)} (with a possible exception for very small ${\displaystyle n}${\displaystyle n}) are composite because of an "algebraic" factorization. Specifically, if ${\displaystyle b}${\displaystyle b} has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. (sequence A070265 in the OEIS)), then the fact that ${\displaystyle x^{m}+1}${\displaystyle x^{m}+1}, with ${\displaystyle m}${\displaystyle m} odd, is divisible by ${\displaystyle x+1}${\displaystyle x+1} shows that ${\displaystyle Q(a^{m},n)}${\displaystyle Q(a^{m},n)} is divisible by ${\displaystyle a^{n}+1}${\displaystyle a^{n}+1} in these special cases. Another case is ${\displaystyle b=4k^{4}}${\displaystyle b=4k^{4}}, with k a positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. (sequence A141046 in the OEIS)), where we have the aurifeuillean factorization.

However, when ${\displaystyle b}${\displaystyle b} does not admit an algebraic factorization, it is conjectured that an infinite number of ${\displaystyle n}${\displaystyle n} values make ${\displaystyle Q(b,n)}${\displaystyle Q(b,n)} prime, notice all ${\displaystyle n}${\displaystyle n} are odd primes.

For ${\displaystyle b=10}${\displaystyle b=10}, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, ... (sequence A097209 in the OEIS), and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (sequence A001562 in the OEIS).

See Repunit#Repunit primes for the list of the generalized Wagstaff primes base ${\displaystyle b}${\displaystyle b}. (Generalized Wagstaff primes base ${\displaystyle b}${\displaystyle b} are generalized repunit primes base ${\displaystyle -b}${\displaystyle -b} with odd ${\displaystyle n}${\displaystyle n})

The least primes p such that ${\displaystyle Q(n,p)}${\displaystyle Q(n,p)} is prime are (starts with n = 2, 0 if no such p exists)

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (sequence A084742 in the OEIS)

The least bases b such that ${\displaystyle Q(b,prime(n))}${\displaystyle Q(b,prime(n))} is prime are (starts with n = 2)

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (sequence A103795 in the OEIS)

• John Renze and Eric W. Weisstein. "Wagstaff prime". MathWorld .
• Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
• Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2^p + 1)/3".
• Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x² − 2 modulo a prime".
• List of repunits in base -50 to 50
• List of Wagstaff primes base 2 to 160

• Classes of prime numbers
• Eponymous numbers in mathematics
• Unsolved problems in number theory