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

:<math> \equiv 25 \pmod{2^p+1}</math> <!--Originally the arrow was only pointing left, but the code example that was below implied that the arrow should've been facing the other way, or maybe even both ways.-->

// Determine if N_p = (2^p + 1)/3 is prime for p > 2

var s = 25

var M = 2^p + 1

var N = M/3

repeat p - 1 times:

s = (s × s) mod M

if s == 25 return PRIME else return COMPOSITE

Known Wagstaff primes

The first few Wagstaff primes are:

:3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ...

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, ...

Generalizations

It is natural to consider more generally numbers of the form

:<math>Q(b,n)=\frac{b^n+1}{b+1}</math>

where the base <math>b \ge 2</math>. Since for <math>n</math> odd we have

:<math>\frac{b^n+1}{b+1}=\frac{(-b)^n-1}{(-b)-1}=R_n(-b)</math>

these numbers are called "Wagstaff numbers base <math>b</math>", and sometimes considered a case of the repunit numbers with negative base <math>-b</math>.

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

However, when <math>b</math> does not admit an algebraic factorization, it is conjectured that an infinite number of <math>n</math> values make <math>Q(b,n)</math> prime, notice all <math>n</math> are odd primes.

For <math>b=10</math>, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … , and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... .

See Repunit#Repunit primes for the list of the generalized Wagstaff primes base <math>b</math>. (Generalized Wagstaff primes base <math>b</math> are generalized repunit primes base <math>-b</math> with odd <math>n</math>)

The least primes p such that <math>Q(n, p)</math> 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, ...

The least bases b such that <math>Q(b, prime(n))</math> 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, ...

References

  • Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
  • Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2<sup>p</sup>&nbsp;+&nbsp;1)/3".
  • Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x<sup>2</sup>&nbsp;&minus;&nbsp;2 modulo a prime" .
  • List of repunits in base -50 to 50
  • List of Wagstaff primes base 2 to 160