Wagstaff prime

Template:Infobox integer sequence In number theory, a Wagstaff prime is a prime number of the form

<math>{{2^p+1}\over 3}</math>

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.

Examples

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

<math>\begin{align}

3 & = {2^3+1 \over 3}, \\[5pt] 11 & = {2^5+1 \over 3}, \\[5pt] 43 & = {2^7+1 \over 3}. \end{align}</math>

Known Wagstaff primes

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... Template: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, ... Template:OEIS

Generalizations

It is natural to consider<ref>Dubner, H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)</ref> 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<ref>Repunit, Wolfram MathWorld (Eric W. Weisstein)</ref> 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. Template:OEIS), 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. Template:OEIS), 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, … Template:OEIS, and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... Template:OEIS.

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, ... Template:OEIS

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, ... Template:OEIS

External links

• Template: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" Template:Webarchive.
• List of repunits in base -50 to 50
• List of Wagstaff primes base 2 to 160