Test de Pépin

En matemàtiques, el test de Pépin (pel matemàtic francés P. Pépin) és un test de primalidad que es pot amprar per a determinar si un número de Fermat és primer. És una variant del test de Proth.

Descripció del test

Siga $F_{n} = 2^{2^{n}} + 1$ el n-ésimo número de Fermat. El test de Pépin establix que per a cada n > 0,

F_{n}

és primer si i només si

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

L'expressió $3^{(F_{n} - 1) / 2}$ es pot evaluar mòdul $F_{n}$ elevant-ho repetidament al quadrat. Açò permet que el test tinga un temps d'eixecució polinòmic, és dir, en principi es tracta d'un algoritme ràpit. No obstant, els números de Fermat creixen tan ràpidament que només es poden evaluar uns pocs en un interval de temps raonable.

També poden amprar-se atres bases en lloc de 3, per eixemple, 5, 6, 7 o 10 (Plantilla:OEIS2).

Demostració de que el test funciona

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

3^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n})

.

Llavors, $3^{F_{n} - 1} \equiv 1 (\mod F_{n})$ , per tant, l'orde multiplicativo de 3 mòdul $F_{n}$ dividix a $F_{n} - 1 = 2^{2^{n}}$ , que és una potència de dos. Per una atra part, l'orde no dividix a $(F_{n} - 1) / 2$ , per lo que deu ser igual a $F_{n} - 1$ . En particular, existixen a lo manco $F_{n} - 1$ números menors que $F_{n}$ que són coprimos en $F_{n}$ , i açò només pot ocórrer si $F_{n}$ és primer.

Per a l'atre sentit, suponga's que $F_{n}$ és primer. Pel criteri de Euler,

3^{(F_{n} - 1) / 2} \equiv (\frac{3}{F_{n}}) (\mod F_{n})

,

a on $(\frac{3}{F_{n}})$ és el símbol de Legendre. Elevant-ho al quadrat repetides voltes, trobem que $2^{2^{n}} \equiv 1 (\mod 3)$ , per tant, $F_{n} \equiv 2 (\mod 3)$ , i $(\frac{F_{n}}{3}) = - 1$ . Com $F_{n} \equiv 1 (\mod 4)$ , concloem que $(\frac{3}{F_{n}}) = - 1$ per 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.

Este artícul conté una traducció derivada de «Test de Pépin» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.