Test de Pépin

En matemàtiques, el test de Pepin és un test de primalitat que es pot emprar per determinar si un nombre de Fermat és primer. És una variant del test de Proth. El test rep el nom pel matemàtic francès P. Pepin.

Descripció del test

Sigui $F_{n}=2^{2^{n}}+1$ l' n -èsim nombre de Fermat. El test de Pepin estableix que per a cada n > 0,

$F_{n}$ és primer si i només si $3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.$

L'expressió $3^{(F_{n}-1)/2}$ es pot avaluar mòdul $F_{n}$ elevant-lo repetidament al quadrat. Això permet que el test tingui un temps d'execució polinòmic, és a dir, en principi es tracta d'un algorisme ràpid. No obstant això, els nombres de Fermat creixen tan ràpidament que només es poden avaluar uns pocs en un interval de temps raonable.

També poden emprar altres bases en lloc de 3, per exemple, 5, 6, 7 o 10.

Demostració que el test funciona

Per a la demostració en un sentit, es parteix de la congruència

$3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}$.

Llavors, $3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}$, per tant, l'ordre multiplicador de mòdul 3 $F_{n}$ divideix $F_{n}-1=2^{2^{n}}$, que és una potència de dos. D'altra banda, l'ordre no divideix $(F_{n}-1)/2$, per la qual cosa ha de ser igual a $F_{n}-1$. En particular, hi ha almenys $F_{n}-1$ nombres menors que $F_{n}$ que són coprimers amb $F_{n}$, i això només pot passar si $F_{n}$ és primer.

Per l'altre sentit, suposem que $F_{n}$ és primer. Pel criteri d'Euler,

$3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}$,

on $\left({\frac {3}{F_{n}}}\right)$ és el símbol de Legendre. Elevant-lo al quadrat repetides vegades, trobem que $2^{2^{n}}\equiv 1{\pmod {3}}$, per tant, $F_{n}\equiv 2{\pmod {3}}$, i $\left({\frac {F_{n}}{3}}\right)=-1$. Com $F_{n}\equiv 1{\pmod {4}}$, vam concloure que $\left({\frac {3}{F_{n}}}\right)=-1$ a causa de la llei de reciprocitat quadràtica.

Referències

• P. Pépin, Sur la formule $2^{2^{n}}+1$ , Comptes Rendus Acad. Sci Paris 85 (1877), pp. 329-333.

Enllaços externs

• The Prime Glossary: Pepin's test