ArithmétiqueThéorème · Glossaire
théorème de Proth
Un nombre de Proth est un entier P = k · 2^n + 1, où k est un entier impair strictement positif, n strictement positif et 2^n > k. Le théorème de Proth affirme que P est premier s’il existe un entier a tel que a^((P−1)/2) ≡ −1 (mod P), ce qui fournit un test efficace pour cette famille d’entiers.
Sommaire
Ce que vous allez apprendre
- Reconnaître un nombre de Proth à partir des conditions sur k et n.
- Appliquer la congruence qui suffit à certifier sa primalité.
- Refaire le calcul complet pour 13 et éviter de conclure sur l'échec d'un seul témoin.
En clair
Prenons 13. On peut l'écrire 3 × 22 + 1 : le multiplicateur 3 est impair et reste inférieur à 22. Treize appartient donc à la famille des nombres de Proth.
Le théorème propose alors un certificat court. On élève un entier bien choisi à une certaine puissance, puis on regarde le reste de la division par 13. Si ce reste vaut 12, c'est-à-dire −1 modulo 13, la primalité de 13 est garantie.
Définition
Le théorème de Proth est un critère de primalité réservé aux nombres de Proth. On appelle ainsi un entier P construit à partir d'un entier impair strictement positif k et d'un entier strictement positif n, avec la condition que 2 élevé à la puissance n soit strictement supérieur à k : .
Pour un tel entier P, on cherche un entier a dont la puissance d'exposant (P − 1)/2 laisse le reste −1 dans la division par P. Cette relation s'écrit . Dès qu'un tel témoin a est trouvé, le théorème assure que P est un nombre premier.
Ce test, dû au mathématicien français François Proth (1852–1879), fournit donc une condition suffisante efficace pour cette famille particulière. La forme k · 2n + 1, à elle seule, ne garantit jamais la primalité.
Le principe
Soit P un nombre de Proth : P = k · 2n + 1, où k est un entier impair strictement positif, n est strictement positif et 2n > k. Si l'on trouve un entier a tel que , alors P est premier.
Le symbole ≡ signifie que la puissance et −1 ont le même reste modulo P. Le calcul porte ainsi sur des restes, sans qu'il soit nécessaire d'écrire la puissance entière.
Quand l'utiliser
Le test exige d'abord une écriture P = k · 2n + 1 avec trois contrôles : k est un entier impair strictement positif, n est un entier strictement positif et 2n est strictement supérieur à k. Il faut ensuite exhiber un entier a qui satisfait exactement la congruence du théorème.
Par exemple, 21 s'écrit 5 × 22 + 1, mais 22 n'est pas supérieur à 5. Cette écriture ne fait donc pas de 21 un nombre de Proth et le théorème ne s'applique pas ; il faut employer un autre test de primalité.
Un exemple, pas à pas
On veut certifier la primalité de 13. Les données choisies sont k = 3, n = 2, P = 13 et le témoin a = 2.
1. Construction : 3 est impair, 2 est strictement positif et 22 = 4 > 3. Ainsi, 13 = 3 × 22 + 1 est bien un nombre de Proth.
2. Exposant : (13 − 1)/2 = 6. Le critère demande donc de calculer 26 modulo 13.
3. Réduction : 26 = 64, puis 64 = 4 × 13 + 12. Le reste est 12, qui représente −1 modulo 13.
4. Verdict : . Toutes les hypothèses étant satisfaites, le théorème de Proth prouve que 13 est premier. Le contrôle est refaisable en vérifiant directement que 64 + 1 = 5 × 13.
En pratique
Face à un entier écrit k · 2n + 1, on contrôle d'abord que k est strictement positif et impair, puis l'inégalité 2n > k. Si l'un de ces contrôles échoue, un test de primalité général est préférable.
Quand la forme convient, on choisit un entier témoin a. L'exponentiation modulaire calcule le reste de a(P−1)/2 sans développer l'immense puissance. Un reste égal à −1 modulo P produit alors un certificat de primalité propre à P.
Pour 13, le choix a = 2 aboutit au reste 12 et conclut immédiatement. Si un choix de a échoue, on ne déclare pas P composé sur ce seul essai : un autre témoin peut réussir.
À ne pas confondre
Un nombre de Proth est défini par sa forme k · 2n + 1 et les conditions sur k et n ; un nombre premier est défini par ses diviseurs. Ainsi, 9 = 1 × 23 + 1 est un nombre de Proth, mais il n'est pas premier puisque 9 = 3 × 3.
Le théorème de Proth n'est pas un simple essai de division. Il recherche une congruence particulière en arithmétique modulaire, tandis que l'essai de division cherche directement un diviseur de P.
Limites et pièges
La frontière 2n = k ne suffit pas : l'inégalité exigée est stricte. Plus généralement, si k est pair, si n n'est pas strictement positif ou si 2n ≤ k, l'entier n'entre pas dans le domaine annoncé du théorème.
Un témoin qui ne donne pas −1 n'établit pas, à lui seul, que P est composé. Pour le nombre premier 13, le choix a = 3 donne 36 ≡ 1 modulo 13, alors que le choix a = 2 donne bien −1. Il faut donc distinguer l'échec d'un essai de l'échec du critère pour tout témoin.
Enfin, réussir la congruence sans avoir d'abord vérifié que P est un nombre de Proth ne permet pas d'invoquer ce théorème. La forme et l'inégalité font partie des hypothèses, pas d'un simple préfiltrage facultatif.
Pour aller plus loin
La fiche arithmétique modulaire approfondit le calcul sur les restes qui rend le test efficace.
La fiche nombre premier replace le verdict de Proth dans la définition générale de la primalité.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres