Dati due qualsiasi numeri $m$ ed $N$ primi tra di loro allora è:
$$ m^{\Phi(N)} = 1 \pmod N $$
o anche
$$ m^{\Phi(N)}- 1 = 0 \pmod N $$
Se poi $N$ è primo allora $\Phi(N) = N - 1$, e si ritrova il piccolo teorema di Fermat.
Questo teorema può considerarsi una conseguenza del teorema di Lagrange.
Infatti se $m$ è primo con $N$ allora appartiene al gruppo moltiplicativo $Z_N$ che ha ordine $\Phi(N)$. Per il corollario del teorema di Lagrange l'ordine di $m$ &è allora un divisore di $\Phi(N)$ e quindi $m^{\ord(m)} = 1 \mod N$ e a maggior ragione $m^{\Phi(N)} = 1 \mod N$.
Consideriamo i seguenti esempi:
| Aritmetica modulo 6 | Aritmetica modulo 8 | Aritmetica modulo 10 |
|---|---|---|
| Φ(6) = 2 | Φ(8) = 4 | Φ(10) = 4 |
0^2 = 0 1^2 = 1 2^2 = 4 [ 4 mod 6 = 4] 3^2 = 3 [ 9 mod 6 = 3] 4^2 = 4 [16 mod 6 = 4] 5^2 = 1 [25 mod 6 = 1] |
0^4 = 0 1^4 = 1 2^4 = 0 [ 16 mod 8 = 0] 3^4 = 1 [ 81 mod 8 = 1] 4^4 = 0 [ 256 mod 8 = 0] 5^4 = 1 [ 625 mod 8 = 1] 6^4 = 0 [ 1296 mod 8 = 0] 7^4 = 1 [ 2401 mod 8 = 1] |
0^4 = 0 1^4 = 1 2^4 = 6 [ 16 mod 10 = 6] 3^4 = 1 [ 81 mod 10 = 1] 4^4 = 6 [ 256 mod 10 = 6] 5^4 = 5 [ 625 mod 10 = 5] 6^4 = 6 [ 1296 mod 10 = 6] 7^4 = 1 [ 2401 mod 10 = 1] 8^4 = 6 [ 4096 mod 10 = 6] 9^4 = 1 [ 6561 mod 10 = 1] |
A prima vista si nota solo una simmetria dei risultati; ma a un esame più attento si nota anche che il risultato vale 1 solo per i numeri primi rispetto all'ordine N: per l'aritmetica di ordine 6 i numeri primi con 6 sono solo due 1 e 5; per l'aritmetica di ordine 8 i numeri primi con 8 sono quattro: 1, 3, 5, 7; per l'aritmetica di ordine 10 i numeri primi con 10 sono quattro: 1, 3, 7, 9. E si nota che l'esponente è proprio il numero di numeri primi con N, in altre parole la funzione di Eulero Φ(N).
Nel 1736 fu proprio Eulero a generalizzare il piccolo teorema di Fermat e a dimostrare questa proprietà che ha preso il nome di teorema di Fermat-Eulero.
Il teorema permette di calcolare l'inverso di un numero in un aritmetica finita.
