Quelle formule donne le petit théorème de Fermat modulo un nombre premier ?
Réponse courte
Si p est premier et a est un entier non divisible par p, alors a^(p−1) ≡ 1 modulo p. Pour tout entier a, on a aussi a^p ≡ a modulo p.
Comprendre
Les deux formes
Le petit théorème de Fermat s’énonce ainsi : si p est premier et si p ne divise pas l’entier a, alors a^(p−1) ≡ 1 (mod p). Une forme équivalente valable pour tout entier a est a^p ≡ a (mod p). La condition de non-divisibilité est nécessaire dans la première écriture.
Exemple de calcul
Avec p=7 et a=3, 3⁶=729=7×104+1, donc 3⁶ ≡ 1 modulo 7. La forme générale donne aussi 3⁷ ≡ 3 modulo 7 ; en effet 2187=7×312+3.
Pourquoi la condition compte
Si a est divisible par p, par exemple a=14 et p=7, alors a⁶ ≡ 0 modulo 7, et non 1. La seconde forme reste juste : 14⁷ et 14 sont tous deux congrus à 0 modulo 7.
Bien distinguer la conclusion
Une congruence signifie que la différence est divisible par p. Le théorème ne dit pas que les puissances sont égales comme entiers. Et il s’applique lorsque le module est premier : remplacer p par un entier composé sans autre justification est une erreur.
Exemples
- p=7, a=3 : 3⁶=729=7×104+1, donc 3⁶ ≡ 1 (mod 7).
- p=7, a=14 : 14⁷ ≡ 14 ≡ 0 (mod 7), mais la formule a^(p−1) ≡1 ne s’applique pas.
Pièges fréquents
- Oublier que p doit être premier et que p ne doit pas diviser a pour la forme a^(p−1) ≡ 1.
- Lire la congruence comme une égalité exacte : 3⁶ n’est pas égal à 1, seule leur différence est divisible par 7.
Pourquoi ça marche
La multiplication par a permute les classes non nulles modulo p quand p ne divise pas a ; comparer les produits mène à la puissance p−1 congrue à 1.
