Théorème d'Euler

Le théorème suivant est une généralisation du petit théorème de Fermat s'appliquant dans les cas où l'on connaît $\phi(n)$.

Théorème 15.3.2   Pour tous $n \geq 2$, $k$ inversible dans $Z/nZ$, $k^{\phi(n)} \equiv 1 \pmod n$.

Par exemple, si $n = 10$, et $k = 3$, alors $\phi(10) = \phi(2.5) = 1.4 = 4$, on a bien

$$\begin{array}{l l l l} 3^4 & \equiv & (3^2)^2 \\ & \equ... ...\equiv & (-1)^2\\ & \equiv & 1 & \pmod{10}\\ \end{array}$$

Si $n = 21$ et $k=4$, alors $\phi(21) = \phi(3.7) = 2.6 = 12$, et on a bien

$$\begin{array}{l l l l} 4^{12} & \equiv & (4^2)^6 \\ & \... ... & \equiv & -20\\ & \equiv & 1 & \pmod{21}\\ \end{array}$$

Propriété 15.3.2   Pour tout $k$ inversible dans $Z/nZ$, l'inverse de $k$ est $k^{\phi(n)-1}$.

Par exemple, si $n = 21$ et $k=4$, l'inverse de $4$ dans $Z/21Z$ est

$$\begin{array}{l l l l} 4^{\phi(21) - 1} & \equiv & 4^{2.6 ... ... \equiv & 16.1\\ & \equiv & 16 & \pmod{21}\\ \end{array}$$

On le vérifie aisément en calculant

$$\begin{array}{l l l l} 4 \times 16 & \equiv & 4.(-5) \\ & \equiv & -20\\ & \equiv & 1 & \pmod{21}\\ \end{array}$$

L'inverse modulo $pq$ ($p$ et $q$ premiers et distincts) de $k$ (inversible dans $Z/pqZ$) est donc $k^{\phi(n) - 1} = k^{(p - 1)(q - 1) - 1}$.