Wagstaff prime

Wagstaff prime

Named after	Samuel S. Wagstaff, Jr.
Publication year	1989[1]
Author of publication	Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.
No. of known terms	44
First terms	3, 11, 43, 683
Largest known term	(2138937+1)/3
OEIS index	A000979 Wagstaff primes: primes of form (2^p + 1)/3

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

${\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}}}$

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}}}$

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

${\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}$", and sometimes considered^[3] a case of the repunit numbers with negative base ${\displaystyle -b}$.

For some specific values of ${\displaystyle b}$, all ${\displaystyle Q(b,n)}$ (with a possible exception for very small ${\displaystyle n}$) are composite because of an "algebraic" factorization. Specifically, if ${\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}$, with ${\displaystyle m}$ odd, is divisible by ${\displaystyle x+1}$ shows that ${\displaystyle Q(a^{m},n)}$ is divisible by ${\displaystyle a^{n}+1}$ in these special cases. Another case is ${\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}$ does not admit an algebraic factorization, it is conjectured that an infinite number of ${\displaystyle n}$ values make ${\displaystyle Q(b,n)}$ prime, notice all ${\displaystyle n}$ are odd primes.

For ${\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}$. (Generalized Wagstaff primes base ${\displaystyle b}$ are generalized repunit primes base ${\displaystyle -b}$ with odd ${\displaystyle n}$)

The least primes p such that ${\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))}$ 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