Qu'est-ce que le petit théorème de Fermat ?
Le petit théorème de Fermat est l'un des piliers de la théorie des nombres. Il affirme que si p est un nombre premier et que a est un entier non divisible par p (autrement dit, PGCD(a, p) = 1), alors a élevé à la puissance (p − 1) laisse un reste de 1 lorsqu'on le divise par p. En notation mathématique : \(a^{p-1} \equiv 1 \pmod{p}\). Une version plus générale est valable pour tout entier a : \(a^{p} \equiv a \pmod{p}\).
Comment utiliser ce calculateur
Saisissez une base a et une valeur p. Le calculateur vérifie si p est premier, calcule PGCD(a, p), puis évalue à la fois \(a^{p-1} \bmod p\) et \(a^{p} \bmod p\) grâce à l'exponentiation modulaire rapide. Lorsque p est premier et que PGCD(a, p) = 1, le premier résultat sera toujours égal à 1 — ce qui confirme le théorème. Si ces conditions ne sont pas réunies, le résultat \(a^{p-1}\) est affiché « n/a », car le théorème ne garantit alors pas une valeur de 1.
La formule expliquée
L'exponentiation modulaire élève la base au carré de façon répétée tout en réduisant modulo p, de sorte que même des exposants très grands restent faciles à gérer. Ce théorème est à la base des tests de primalité (le test de Fermat), des calculs de clés du chiffrement RSA et de la recherche d'inverses modulaires, puisque \(a^{p-2} \bmod p\) donne l'inverse de a modulo un nombre premier p.
Exemple détaillé
Prenons a = 2 et p = 7. Comme 7 est premier et que PGCD(2, 7) = 1, on s'attend à $$2^{6} \bmod 7 = 64 \bmod 7 = 1.$$ ✔ La forme générale donne $$2^{7} \bmod 7 = 128 \bmod 7 = 2,$$ ce qui est bien égal à \(a \bmod 7 = 2\). ✔
Foire aux questions
Et si p n'est pas premier ? Le théorème peut être pris en défaut. Le calculateur signale alors que p n'est pas premier et seule la valeur générale \(a^{p} \bmod p\) a du sens, sans être nécessairement égale à a.
Et si a est un multiple de p ? Dans ce cas, PGCD(a, p) ≠ 1, donc \(a^{p-1} \bmod p\) ne vaudra pas 1 (il vaut 0). La forme générale \(a^{p} \equiv a\) reste néanmoins valable.
Puis-je l'utiliser pour trouver des inverses modulaires ? Oui — pour un nombre premier p, \(a^{p-2} \bmod p\) est l'inverse multiplicatif de a modulo p.
