Théorème d'Euler
Nous pouvons à présent énoncer et même démontrer le théorème d'Euler.
Théorème d'Euler
Si $(a,n) = 1$, alors $$a^{\varphi(n)} \equiv 1 \pmod n$$ où $\varphi$ désigne la fonction indicatrice d'Euler.
Ce théorème nous indique donc que, dans la suite des puissances successives de $a$, nous retomberons toujours sur $1$ à la puissance $\varphi(n)$-ème. À noter cependant qu'il ne s'agit pas spécialement de la première fois où un $1$ apparaît à nouveau. Nous discuterons de cela dans le prochain point théorique.
Démonstration
NB : Nous travaillons modulo $n$ dans cette preuve et ne différencions donc pas deux nombres qui sont égaux modulo $n$.
Notons $A = \left\{a_1, a_2, \ldots, a_k\right\}$ l'ensemble des entiers de $\left\{0, 1, \ldots, n-1\right\}$ qui sont premiers avec $n$. On a donc $\#A = \varphi(n)$ par définition de la fonction indicatrice d'Euler (d'où $k = \varphi(n)$).
Remarquons à présent que si nous multiplions tous les éléments de $A$ par $a$ (celui de l'énoncé), alors les éléments de $A$ sont simplement permutés, c'est-à-dire
$$A = \left\{aa_1,aa_2, \ldots, aa_k\right\}.$$ Cela vient du fait que si $(a_j, n) = 1$, alors $(aa_j, n) = 1$ également puisque $a$ est premier avec $n$ (donc $a_j \in A \Rightarrow aa_j \in A$). De plus, deux éléments $a_i$ et $a_j$ distincts, lorsqu'ils sont multipliés par $a$, restent distincts (modulo $n$). En effet, si tel n'était pas le cas, on aurait $aa_i \equiv aa_j$ mais une simple multiplication par $a^{-1}$ rendrait $a_i \equiv a_j$ qui est impossible vu que $a_i$ et $a_j$ étaient supposés différents.
Pour mieux comprendre ce phénomène, regardons ce que cela signifie pour $n = 8$ et $a = 5$. Dans ce cas, on a $A = \left\{1, 3, 5, 7\right\}$ et, en multipliant chaque élément par $5$, on obtient $\left\{5, 15, 25, 35\right\} = \left\{5, 7, 1, 3\right\}$ (comme nous travaillons modulo $8$). Nous sommes donc bien retombés sur les éléments de $A$.
Reprenons la preuve en général. Les éléments de $A$ étant exactement les mêmes que ceux de $\left\{aa_1,aa_2, \ldots, aa_k\right\}$; multiplier entre eux tous les éléments de $A$ revient exactement à multiplier ceux de $\left\{aa_1,aa_2, \ldots, aa_k\right\}$. On a donc
$$\begin{align}
a_1 \cdot a_2 \cdot \ldots \cdot a_k & \equiv aa_1 \cdot aa_2 \cdot \ldots \cdot aa_k \pmod n\\
& \equiv a^k \cdot a_1 \cdot \ldots \cdot a_k \pmod n.
\end{align}$$ Les éléments $a_1, \ldots, a_k$ étant tous inversibles, nous pouvons multiplier les deux membres de cette dernière égalité par $a_1^{-1} \cdot \ldots \cdot a_k^{-1}$ pour obtenir
$$1 \equiv a^k \pmod n$$ qui est exactement l'énoncé du théorème d'Euler puisque $k = \varphi(n)$.
Remarque : Si $(a,n) \neq 1$, alors il est aisé de comprendre que la seule puissance de $a$ donnant $1$ modulo $n$ est $a^0 = 1$. En effet, pour $m > 0$, $a^m$ partage un facteur avec $n$ et $a^m - 1$ ne peut dès lors pas être divisible par $n$. Dans un tel cas, il convient alors de séparer $n$ en sa partie possédant des facteurs communs avec $a$ et celle première avec $a$ pour analyser les puissances de $a$ à l'aide du théorème d'Euler.
Théorème de Fermat
Le théorème de Fermat (nous parlons ici du petit théorème de Fermat, le grand étant bien différent) est un corollaire immédiat du théorème d'Euler. Il s'agit du cas particulier où $n$ est un nombre premier.
Théorème de Fermat
Si $a$ n'est pas divisible par $p$ premier, alors
$$a^{p-1} \equiv 1 \pmod p.$$