Vés al contingut

Test de Pépin

De la Viquipèdia, l'enciclopèdia lliure

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]

Sigui l' n -èsim nombre de Fermat. El test de Pepin estableix que per a cada n > 0,

és primer si i només si

L'expressió es pot avaluar mòdul 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]

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

.

Llavors, , per tant, l'ordre multiplicador de mòdul 3 divideix , que és una potència de dos. D'altra banda, l'ordre no divideix , per la qual cosa ha de ser igual a . En particular, hi ha almenys nombres menors que que són coprimers amb , i això només pot passar si és primer.

Per l'altre sentit, suposem que és primer. Pel criteri d'Euler,

,

on és el símbol de Legendre. Elevant-lo al quadrat repetides vegades, trobem que , per tant, , i . Com , vam concloure que a causa de la llei de reciprocitat quadràtica.

Referències

[modifica]
  • P. Pépin, Sur la formule , Comptes Rendus Acad. Sci Paris 85 (1877), pp. 329-333.

Enllaços externs

[modifica]