test de Pépin

Prenons le nombre de Fermat F₂, qui vaut 17. Pour savoir s’il est premier, le test de Pépin demande de calculer une puissance de 3, puis de ne garder que son reste dans la division par 17.

Le reste obtenu est 16, c’est-à-dire −1 modulo 17. Ce résultat suffit pour conclure que 17 est premier. Le même verdict, avec un exposant adapté, vaut pour tout nombre de Fermat F_n lorsque n est au moins égal à 2.

Le test de Pépin est un critère de primalité réservé aux nombres de Fermat. Pour un entier n au moins égal à 2, le nombre de Fermat d’indice n, noté F_n, est défini par la formule suivante.

Le critère affirme que F_n est premier si et seulement si la puissance de base 3 et d’exposant (F_n − 1) / 2 laisse le même reste que −1 dans la division par F_n. En notation de congruence, cela s’écrit $3^{(F_n-1)\mathrm{/}2}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}{F}_n)3^\{(F\_n-1)/2\}\; \backslash equiv\; -1\; \backslash pmod\{F\_n\}$. Le « si et seulement si » donne les deux verdicts : la congruence réussie prouve la primalité, tandis que son échec prouve que le nombre est composé. Aucune recherche des facteurs de F_n n’est nécessaire.

Appliquons le test au nombre de Fermat d’indice 2. Les données sont n = 2, F₂ = 2⁴ + 1 = 17 et l’exposant (17 − 1) / 2 = 8. Il faut donc déterminer le reste de 3⁸ dans la division par 17.

1. On élève d’abord 3 au carré : 3² = 9.

2. On élève 9 au carré : 3⁴ = 81. Comme 81 = 4 × 17 + 13, le reste est 13.

3. On élève 13 au carré : 3⁸ a le même reste que 169. Or 169 = 9 × 17 + 16, donc ce reste est 16, c’est-à-dire −1 modulo 17.

Le critère de Pépin est satisfait : F₂ = 17 est premier. Pour contrôler le calcul directement, on peut aussi vérifier que 3⁸ = 6 561 = 386 × 17 − 1.

Pour tester un nombre de Fermat F_n avec n ≥ 2, on calcule la puissance de 3 modulo F_n. Le calcul modulaire évite de conserver l’immense puissance entière : après chaque multiplication, on remplace le résultat par son reste.

L’exponentiation rapide est préférable à des multiplications répétées. Elle décompose l’exposant en puissances de 2 et réduit chaque carré modulo F_n, comme dans le calcul pour F₂.

Si le reste final diffère de F_n − 1, le nombre est composé, même si aucun facteur n’est encore connu. Si le reste vaut F_n − 1, le test prouve au contraire que ce nombre de Fermat est premier.

Le test de Pépin ne se confond pas avec un test de primalité général. Son entrée doit être un nombre de Fermat F_n avec n ≥ 2 ; pour 19, qui n’est pas de cette forme, ce critère ne s’applique pas.

Il ne se confond pas non plus avec la factorisation. Un reste différent de F_n − 1 prouve que F_n est composé, mais ne donne pas automatiquement ses facteurs. Le verdict et la recherche des diviseurs sont deux tâches distinctes.

Le domaine annoncé commence à n = 2. Il ne faut donc pas étendre mécaniquement cette formulation à F₀ = 3 : la puissance testée vaut alors 3, soit 0 modulo 3, alors que 3 est premier.

Le symbole −1 modulo F_n désigne le même reste que F_n − 1. Dans l’exemple, le calculateur peut afficher 16 plutôt que −1 ; ces deux écritures donnent bien le même verdict modulo 17.

Un échec du test établit seulement que le nombre de Fermat est composé. Chercher ensuite un diviseur exige une méthode de factorisation distincte ; il serait erroné de lire le reste final comme un facteur.

La fiche nombre de Fermat précise la famille particulière d’entiers à laquelle le test de Pépin s’applique.

La fiche congruence modulo n approfondit la notion de reste qui porte tout le verdict du test.

La fiche test de primalité replace le critère de Pépin parmi les méthodes qui décident si un entier est premier.