Un énoncé de théorie des nombres selon lequel pour un nombre premier p et un entier a, a^p ≡ a (mod p) ; équivalemment, si a n'est pas divisible par p alors a^(p-1) ≡ 1 (mod p).

Principe

Résulte du fait que le groupe multiplicatif des entiers modulo un premier p est cyclique d'ordre p−1, de sorte que l'élévation aux puissances respecte l'ordre du groupe et conduit à ces congruences.

Démonstration

Pour p=7 et a=3, 3^6 = 729 ≡ 1 (mod 7), ce qui vérifie le théorème ; si a est multiple de p la congruence a^p ≡ a est trivialement vraie.

Mauvaise application

Utiliser le théorème pour certifier la primalité sans tenir compte des composés satisfaisant la congruence pour plusieurs bases (nombres de Carmichael) ou appliquer la forme réduite modulo un composé sans conditions.

Conséquence

Fournit une identité d'exponentiation modulaire rapide employée dans les tests de primalité, le calcul d'inverses modulaires lorsque le module est premier, et dans de nombreux algorithmes de théorie des nombres computationnelle et de cryptographie.

Inversion

Le théorème d'Euler généralise cet énoncé aux modules composés en remplaçant p−1 par la fonction indicatrice d'Euler φ(n) ; inverser l'énoncé le ramène à des affirmations sur l'ordre de groupes dans des anneaux finis arbitraires.

Limite

Valide seulement lorsque le module est premier pour l'exposant p ou pour des entiers premiers avec p dans la forme p−1 ; n'implique pas la primalité et ne vaut pas pour des modules composés arbitraires.

Tension sémantique

Conflit conceptuel avec le théorème d'Euler et les contre-exemples de Carmichael : la congruence de Fermat est une propriété forte et facile à vérifier pour les nombres premiers mais insuffisante seule pour tester la primalité en présence de pseudopremiers.

Synthèse

Une congruence fondamentale reliant modules premiers et exponentiation : les puissances d'entiers se réduisent de façon prévisible modulo un premier en raison de l'ordre fini du groupe multiplicatif.