Test de Pépin

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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}\equiv1 \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 (\frac3{F_n}\right) \pmod{F_n},

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

Referències[modifica | modifica el codi]

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

Enllaços externs[modifica | modifica el codi]