Pour un entier $n \ge 1$, l’indicateur d’Euler, noté $\varphi(n)$, est une fonction qui compte le nombre d’entiers naturels compris entre 1 et $n$ qui sont premiers avec n (c’est-à-dire dont le plus grand commun diviseur avec $n$ est 1).
- Exemple : Pour $n=10$, les nombres premiers avec 10 sont 1, 3, 7, 9. Il y en a 4, donc $\varphi(10)=4$.
- Si $p$ est un nombre premier, tous les nombres de 1 à $p-1$ sont premiers avec $p$. Donc, $\varphi(p) = p-1$.
La fonction $\varphi(n)$ correspond aussi à l’ordre (le nombre d’éléments) du groupe des inversibles de l’anneau $\mathbb{Z}/n\mathbb{Z}$.
Si $a$ et $n$ sont deux entiers premiers entre eux, alors $a$ élevé à la puissance $\varphi(n)$ est congru à 1 modulo $n$.
En notation modulaire : $$ a^{\varphi(n)} \equiv 1 \pmod{n} $$
Remarque
Le petit théorème de Fermat est un cas particulier du théorème d’Euler. Si $n=p$ est un nombre premier, alors $\varphi(p) = p-1$. Pour tout entier $a$ non divisible par $p$ (donc premier avec $p$), le théorème d’Euler donne $a^{p-1} \equiv 1 \pmod{p}$, ce qui est bien la deuxième version du petit théorème de Fermat.
Démonstration (utilisant la théorie des groupes)
Cette démonstration est élégante et met en lumière la structure sous-jacente au théorème.
- Considérer le groupe des inversibles : On considère l’ensemble des classes de congruence modulo $n$ qui sont premières avec $n$. Cet ensemble, muni de la multiplication modulo $n$, forme un groupe abélien, noté $(\mathbb{Z}/n\mathbb{Z})^\times$.
- Ordre du groupe : Par définition de la fonction $\varphi(n)$, l’ordre (le nombre d’éléments) de ce groupe est exactement $\varphi(n)$.
- Appliquer le théorème de Lagrange : Le théorème de Lagrange, un résultat fondamental de la théorie des groupes, stipule que pour tout groupe fini $G$, si on prend un élément $g \in G$, alors $g$ élevé à la puissance de l’ordre du groupe est égal à l’élément neutre. $$ g^{|G|} = e $$
- Conclusion : On applique ce résultat à notre groupe. Soit $a$ un entier premier avec $n$. Sa classe de congruence, notée $\bar{a}$, est un élément du groupe $(\mathbb{Z}/n\mathbb{Z})^\times$. L’ordre de ce groupe est $\varphi(n)$ et son élément neutre est la classe $\bar{1}$. Le théorème de Lagrange nous donne donc : $$ (\bar{a})^{\varphi(n)} = \bar{1} $$ En revenant à la notation des congruences, cela s’écrit : $$ a^{\varphi(n)} \equiv 1 \pmod{n} $$ Ce qui achève la démonstration.
Implications et Utilisation
- Cryptographie (RSA) : Le théorème d’Euler est le cœur de l’algorithme RSA. Dans cet algorithme, on utilise un module $n=pq$ (produit de deux grands nombres premiers). On a alors $\varphi(n) = (p-1)(q-1)$. Le théorème garantit que pour un message $M$, si on le chiffre par $C \equiv M^e \pmod{n}$ et qu’on le déchiffre par $M’ \equiv C^d \pmod{n}$, avec $ed \equiv 1 \pmod{\varphi(n)}$, alors on retrouve bien $M’ \equiv M \pmod{n}$. Le théorème d’Euler assure que cette « boucle » fonctionne.
- Réduction des puissances : Il permet de simplifier des calculs de grandes puissances en arithmétique modulaire. Par exemple, pour calculer $3^{100} \pmod{10}$, on sait que $\varphi(10)=4$. Comme 3 et 10 sont premiers entre eux, $3^4 \equiv 1 \pmod{10}$. Donc $3^{100} = (3^4)^{25} \equiv 1^{25} \equiv 1 \pmod{10}$.