Résultat en théorie des nombres : pour des entiers a et n tels que gcd(a,n)=1, on a a^{φ(n)} ≡ 1 (mod n), où φ(n) est la fonction indicatrice d'Euler qui compte les unités de (Z/nZ)×.

Principe

Le groupe multiplicatif des unités modulo n a pour ordre φ(n), donc par le théorème de Lagrange toute unité élevée à l'ordre du groupe est congrue à l'identité modulo n.

Démonstration

Exemple : a=3, n=10 donne φ(10)=4 et 3^4=81≡1 (mod 10). De façon générale, on peut réduire des exposants modulo φ(n) pour calculer des puissances de unités.

Mauvaise application

Appliquer la congruence lorsque gcd(a,n)≠1 (par exemple si a et n ne sont pas premiers entre eux) ou supposer que φ(n) est l'exposant minimal pour toutes les unités ; l'exposant universel minimal peut être la fonction de Carmichael λ(n).

Conséquence

Fournit des règles de réduction d'exposants en arithmétique modulaire et sous-tend la correction et des étapes clés des protocoles cryptographiques et algorithmes fondés sur l'exponentiation modulaire.

Inversion

Le petit théorème de Fermat est le cas particulier n premier ; inversement, l'existence de la congruence pour tous les a premiers à n impose des contraintes structurelles sur le groupe multiplicatif de (Z/nZ)×.

Limite

Suppose que a et n sont entiers avec gcd(a,n)=1 ; elle n'affirme pas quel est l'exposant minimal qui envoie chaque unité sur 1 (cette information relève de λ(n)) et ne s'applique pas aux diviseurs de zéro modulaires.

Tension sémantique

Fréquemment confondu avec le petit théorème de Fermat ou avec des énoncés sur les ordres d'éléments individuels ; le théorème d'Euler exprime un fait sur l'ordre du groupe, pas sur l'existence de racines primitives ou d'exposants minimaux pour toutes les unités.

Synthèse

Le théorème d'Euler formalise le fait que les unités modulo n forment un groupe fini d'ordre φ(n), donnant la congruence pratique a^{φ(n)}≡1 pour réduire des exposants et relier la structure multiplicative à l'arithmétique modulaire.