Calculateur du petit théorème de Fermat
Vérifiez le petit théorème de Fermat en ligne : saisissez une base a et un nombre premier p. Il calcule a^(p-1) mod p et vérifie si le résultat est égal à 1. Utile en théorie des nombres, pour les tests de primalité et en cryptographie.
Vérifier le petit théorème de Fermat ou calculer des puissances modulo
Formule du petit théorème de Fermat
Où :
- \(p\) — un nombre premier (le module)
- \(a\) — un entier tel que \(1 \le a < p\), c’est-à-dire non divisible par \(p\)
- \(a^{p-1} \bmod p\) — le reste de la division de \(a^{p-1}\) par \(p\)
Le théorème affirme que, pour tout nombre premier \(p\) et tout entier \(a\) non divisible par \(p\), élever \(a\) à la puissance \(p-1\), puis le réduire modulo \(p\), donne toujours un reste de 1. Une forme équivalente, \(a^p \equiv a \pmod{p}\), est valable pour tous les entiers \(a\), y compris les multiples de \(p\).
Petit théorème de Fermat – Exemple de calcul
Exemple : prenons les valeurs par défaut \(a = 5\) et \(p = 7\). Puisque 7 est premier et que 5 n’est pas divisible par 7, le théorème doit s’appliquer.
\[a^{p-1} \bmod p = 5^{7-1} \bmod 7 = 5^6 \bmod 7\]
\[5^6 = 15625, \qquad 15625 = 7 \times 2232 + 1 \;\Rightarrow\; 15625 \bmod 7 = 1\]
Résultat : \(5^6 \equiv 1 \pmod{7}\), donc le théorème est vérifié. ✅
Comment utiliser le calculateur
- Saisissez la base \(a\) dans le champ Base (a). Elle doit respecter \(1 \le a < p\).
- Saisissez un nombre premier dans le champ Module premier (p) (par exemple 2, 3, 5, 7, 11…).
- Lisez le Résultat de a^(p-1) mod p : c’est le reste de la division de \(a^{p-1}\) par \(p\).
- Vérifiez Théorème vérifié ? : « Oui » s’affiche lorsque le reste est égal à 1, ce qui est le cas pour toute saisie valide.
Si vous saisissez un module non premier, une base hors de l’intervalle autorisé ou \(a \ge p\), le calculateur affiche un message d’erreur au lieu d’un résultat.
Que signifie le petit théorème de Fermat ?
Énoncé par Pierre de Fermat en 1640, le petit théorème de Fermat est l’un des fondements de la théorie élémentaire des nombres. Il montre que les nombres premiers imposent une structure remarquablement régulière aux puissances : quelle que soit la base \(a\) choisie (tant que \(p\) ne divise pas \(a\)), la puissance \(a^{p-1}\) est toujours exactement congrue à 1 modulo \(p\). Autrement dit, \(a^{p-1}\) est toujours égal à un multiple de \(p\) plus un.
Pourquoi est-ce important ? D’abord, c’est un raccourci de calcul puissant. Au lieu de calculer directement une puissance énorme comme \(3^{100}\), vous pouvez réduire l’exposant modulo \(p-1\) et travailler avec des nombres beaucoup plus petits — une technique constamment utilisée en arithmétique modulaire. Ensuite, le théorème sert aux tests de primalité : si \(a^{p-1} \bmod p \ne 1\) pour une certaine valeur de \(a\), alors \(p\) n’est certainement pas premier. C’est le principe du test de Fermat et, sous une forme perfectionnée, du test de Miller-Rabin utilisé pour trouver de grands nombres premiers.
Enfin, le théorème est essentiel en cryptographie. Le chiffrement et le déchiffrement RSA reposent avant tout sur des exponentiations modulaires, et c’est le petit théorème de Fermat (avec sa généralisation, le théorème d’Euler) qui garantit que le déchiffrement d’un message permet de retrouver l’original. Il conduit aussi directement à la formule permettant de trouver les inverses multiplicatifs modulo un nombre premier : puisque \(a^{p-1} \equiv 1 \pmod{p}\), l’inverse de \(a\) est simplement \(a^{p-2} \bmod p\).
Comment interpréter le résultat
Pour toute saisie valide — un nombre premier \(p\) et une base \(a\) telle que \(1 \le a < p\) — le calculateur renverra toujours 1 et « Oui ». C’est précisément ce qu’affirme le théorème : il concerne toutes ces paires, et non seulement certaines. Pour voir pourquoi il ne s’applique pas aux nombres non premiers, essayez \(a = 2\), \(p = 9\) : \(2^8 = 256\) et \(256 \bmod 9 = 4 \ne 1\). Le théorème fournit un test à sens unique : un nombre non premier échoue toujours pour au moins une base, tandis qu’un test réussi ne prouve pas à lui seul la primalité (voir la remarque sur les nombres de Carmichael ci-dessous).
Conditions, limites et conseils
- Le module doit être premier. Le théorème ne s’applique pas, en général, aux modules composés. Pour un nombre composé \(n\), utilisez plutôt le théorème d’Euler avec \(a^{\varphi(n)} \equiv 1 \pmod{n}\), où \(\varphi\) est l’indicatrice d’Euler et \(\gcd(a, n) = 1\).
- La base ne doit pas être divisible par \(p\). Si \(a \equiv 0 \pmod{p}\), alors \(a^{p-1} \equiv 0\), et non 1. La forme équivalente \(a^p \equiv a \pmod{p}\) reste valable dans ce cas.
- Les tests de Fermat peuvent être trompés. Il existe des nombres composés appelés nombres de Carmichael (le plus petit est 561) qui vérifient \(a^{n-1} \equiv 1 \pmod{n}\) pour tout \(a\) premier avec \(n\). Un seul test réussi ne constitue donc pas une preuve de primalité.
- Réduisez les exposants. Pour les calculs à la main, combinez le théorème avec les élévations au carré successives : réduisez les exposants modulo \(p-1\) et les produits intermédiaires modulo \(p\) pour garder des nombres petits.
- Outils associés. Pour les systèmes de congruences, consultez le calculateur du théorème des restes chinois ; pour la division en arithmétique modulaire, le calculateur d’inverse multiplicatif modulo est un complément naturel.
Questions fréquentes
Qu’est-ce que le dernier théorème de Fermat ? Est-ce la même chose ?
Non, ce sont deux résultats différents, souvent confondus à cause de leurs noms. Le petit théorème de Fermat (1640) porte sur l’exponentiation modulaire : a^(p-1) ≡ 1 (mod p) lorsque p est premier. Le dernier théorème de Fermat affirme qu’aucun entier positif x, y, z ne vérifie x^n + y^n = z^n pour n > 2 ; Fermat en avait formulé la conjecture, mais celle-ci n’a été démontrée qu’en 1995 par Andrew Wiles.