Nombre primer de Wagstaff

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

p = 2 q + 1 3 {\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 p = 2 p + 1 3 {\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 x 2 − 2 {\displaystyle x^{2}-2} d'un nombre de Wagstaff.[cal citació]

Generalitzacions

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

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

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

b n + 1 b + 1 = ( − b ) n − 1 ( − b ) − 1 = R n ( − b ) {\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 Q ( b , n ) {\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 x m + 1 {\displaystyle x^{m}+1} amb m {\displaystyle m} senar sigui divisible per x + 1 {\displaystyle x+1} indica que Q ( a m , n ) {\displaystyle Q(a^{m},n)} és divisible per a n + 1 {\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 b = 4 k 4 {\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 Q ( b , n ) {\displaystyle Q(b,n)} sigui primer.[6]

Referències

  1. ↑ 1,0 1,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: (242737 + 1)/3 a PrimePages.
  4. ↑ Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof. 
  5. ↑ Dubner H. and Granlund, T.: Primes of the Form (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
  6. ↑ 6,0 6,1 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)