Nombre primer de Wagstaff

Un nombre primer de Wagstaff és un nombre primer p de la forma

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

on q és un altre nombre primer senar. Segons la pàgina PrimePages, François Morain els va anomenar així en honor del matemàtic Samuel S. Wagstaff Jr. a la conferència Eurocrypt de l'any 1990.^[1] Estan relacionats amb la nova conjectura de Marsenne i tenen aplicacions dins del camp de la criptologia.^[2]

Els primers nombres primers de Wagstaff són:

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

La seqüència de nombres primers de Wagstaff es pot consultar a l'OEIS A000979

Els primers exponents coneguts que produeixen primers de Wagstaff o primers probables són:

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, ...^[1]

La seqüència d'exponents de Wagstaff es pot consultar a l'OEIS A000978

Es conjectura que si p és un nombre primer de Wagstaff superior a 43, llavors ${\displaystyle p={{2^{p}+1} \over 3}}$ és sempre compost.^{[cal citació]}

Proves de primalitat

La primalitat de p ha estat demostrada certa o bé falsa per cada q fins a cert llindar, per sobre del qual tots els valors p obtinguts es consideren primers probables.

Al 2007, François Morain va provar la primalitat de q = 42737 amb una implementació del test de primalitat de corba el·líptica (Elliptic Curve Primality Proof, ECPP) distribuïda, que s'executa en diverses xarxes d'estacions de treball en un processador Opteron.^[3][4]

L'eina LLR (Lucas-Lehmer-Riesel) creada per Jean Penné és utilitzada per trobar primers probables de Wagstaff mitjançant el test de Vrba-Reix; un test PRP basat en les propietats d'un cicle del digraf sota el mòdul ${\displaystyle x^{2}-2}$ d'un nombre de Wagstaff.^{[cal citació]}

Generalitzacions

Es poden considerar^[5] nombres més generalitzats de la forma

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

on la base ${\displaystyle b\geq 2}$. Per cada ${\displaystyle n}$ senar tenim

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

aquests nombres s'anomenen Nombres primers de Wagstaff en base b, i són considerats un cas dels nombres de repunit amb base negativa -b.^[6]

Per alguns valors específics de b, tots els valors ${\displaystyle Q(b,n)}$ (amb algunes possibles excepcions per n molt petites) són compostos degut a una factorització algebraica. Específicament, si b té la forma d'una potència perfecta amb exponent senar (8, 27, 32, 64, 125...) llavors el fet que ${\displaystyle x^{m}+1}$ amb ${\displaystyle m}$ senar sigui divisible per ${\displaystyle x+1}$ indica que ${\displaystyle Q(a^{m},n)}$ és divisible per ${\displaystyle a^{n}+1}$ en aquests casos especials.

La seqüència de potències perfectes amb exponent senar es troba a l'OEIS A070265

Un altre cas és ${\displaystyle b=4k^{4}}$ amb k sent un enter positiu (4, 64, 324, 1024, 2500...), on tenim una factorització aurifeuïlleana.

La seqüència dels valors de k també es pot trobar a l'OEIS A141046

Tot i així, quan b no admet una factorització alebraica, és conjecturat que un nombre infinit de valors senars n fan que ${\displaystyle Q(b,n)}$ sigui primer.^[6]

Referències

1. «Top Twenty's Home Page». The Prime Pages. Arxivat de l'original el 20 novembre 2020. [Consulta: 9 desembre 2020].
2. Bateman, P. T.; Selfridge, J. L.; Wagstaff, Jr., S. S. «The New Mersenne Conjecture». American Mathematical Monthly, 96, 1989, pàg. 125–128. DOI: 10.2307/2323195. JSTOR: 2323195.
3. Comentari fet per François Morain, The Prime Database: (2⁴²⁷³⁷ + 1)/3 a PrimePages.
4. Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof. 
5. Dubner H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
6. Repunit, Wolfram MathWorld (Eric W. Weisstein)

Enllaços externs

• Els primers de Wagstaff en base b=10 es troben a (successió A097209 a l'OEIS), amb valors n corresponents a (successió A001562 a l'OEIS).
• El mínim primer p tal que Q(n, p) és primer es troba a (successió A084742 a l'OEIS)
• La mínima base b tal que Q(b, prime(n)) és primer es troba a (successió A103795 a l'OEIS)