Reprenons nos exemples initiaux et observons ce que le théorème d'Euler nous a apporté. Il ne nous a évidemment rien appris de plus que ce que l'on connaissait déjà vu que nos exemples étaient très petits, mais nous pouvons observer sur ceux-ci la puissance du théorème.
Pour $n = 5$ et $a = 2$, nous avions
$$\begin{array}{c|cccccccc}
m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\[2ex]
\hline
2^m \pmod 5 & 1 & 2& 4 & 3 & \boxed{1} & 2 & 4 &\ldots
\end{array}$$ Le théorème d'Euler (en fait, le théorème de Fermat vu que $5$ est premier), nous indique dans ce cas que
$$2^4 \equiv 1 \pmod 5.$$ Il s'agit du $1$ encadré dans notre tableau, et on remarque qu'il s'agit en fait de la première fois où $1$ réapparaît.
Pour $n = 7$ et $a = 2$, nous avions par contre
$$\begin{array}{c|cccccccc}
m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\[2ex]
\hline
2^m \pmod 7 & 1 & 2& 4 & 1 & 2 & 4 &\boxed{1} & \ldots
\end{array}$$ et le théorème de Fermat nous apporte ici
$$2^6 \equiv 1 \pmod 7.$$ Il ne s'agit cette fois-ci pas de la première fois que le nombre $1$ réapparaît.
Ordre multiplicatif d'un nombre modulo $n$
Vu que $\varphi(n)$ n'est visiblement pas toujours la plus petite puissance strictement positive qu'il faut mettre à l'entier $a$ pour obtenir $1$ modulo $n$, il est naturel de donner un nom et une notation à cette plus petite puissance.
Petites propriétés
Les propriétés suivantes ne sont pas difficiles mais sont souvent bien utiles.
Propriété 1
Si $(a,n)=1$, alors $a^m \equiv 1 \pmod n$ avec $m \in \mathbb{N}$ si et seulement si $o_n(a)$ divise $m$.
Démonstration
Le sens $\Leftarrow$ est le plus facile. Si $o_n(a)$ divise $m$, cela signifie que $m = o_n(a)\cdot k$ pour un entier $k$. Dès lors, vu que $a^{o_n(a)} \equiv 1 \pmod n$ par définition de l'ordre multiplicatif, on a
$$a^m \equiv a^{o_n(a)\cdot k} \equiv \left(a^{o_n(a)}\right)^k \equiv 1^k \equiv 1 \pmod n.$$ Pour le sens $\Rightarrow$, on considère la division euclidienne de $m$ par $o_n(a)$ :
$$m = q\cdot o_n(a) + r \quad \text{où} \quad r \in \left\{0, \ldots, o_n(a)-1\right\}.$$ On a alors
$$1 \equiv a^m \equiv a^{q\cdot o_n(a) + r}\equiv \left(a^{o_n(a)}\right)^q \cdot a^r \equiv a^r \pmod n.$$ Vu que $r$ est un naturel inférieur à $o_n(a)$, on doit forcément avoir $r = 0$. En effet, sinon on aurait trouvé un exposant non nul inférieur à $o_n(a)$ tel que $a^r$ rend $1$ modulo $n$, ce qui est impossible vu que $o_n(a)$ est le plus petit nombre vérifiant cette propriété.
Proposition 2
Si $(a,n) = 1$, $o_n(a)$ divise $\varphi(n)$.
Démonstration
Il s'agit là d'une réécriture du théorème d'Euler à l'aide de $o_n(a)$. En effet, la propriété précédente nous montre que le théorème $a^{\varphi(n)} \equiv 1 \pmod n$ est équivalent à dire que $o_n(a)$ divise $\varphi(n)$.
Proposition 3
Si $(a,n) = 1$, les nombres $a^0, a^1, a^2, \ldots, a^{o_n(a)-1}$ sont distincts deux à deux modulo $n$.
Démonstration
On procède par l'absurde. Supposons avoir $i, j \in \left\{0, 1, \ldots, o_n(a)-1\right\}$ distincts tels que $a^i \equiv a^j \pmod n$. On peut sans perte de généralité supposer que $i > j$. Vu que $a$ est inversible modulo $n$, on peut multiplier les deux membres par $a^{-j}$ pour obtenir
$$a^{i-j} \equiv 1 \pmod n.$$ Il s'agit là d'une contradiction, car nous avons trouvé un exposant ($i-j$) non nul et inférieur à $o_n(a)$ qui donne $1$ modulo $n$.
Retour sur notre exemple
Pour $n = 7$ et $a = 2$, nous avons vu plus haut que $o_n(a) = 3$. On peut vérifier que les trois propriétés ci-dessus sont bien correctes :
- On voit bien sur notre tableau que $2^m \equiv 1 \pmod 7$ si et seulement si $m$ est un multiple de $3$.
- $\varphi(7) = 6$ est bien divisible par $3$.
- Les nombres $2^0$, $2^1$ et $2^2$ sont égaux à $1$, $2$ et $4$ respectivement qui sont bien différents modulo $7$. Il s'agit en fait de la suite de nombres qui apparaît périodiquement.