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.

Et maintenant ?

Questions proches

← Toutes les questions-réponses