Teoria dei numeri - Atitmetiche finite
Il Teorema di Fermat-Eulero
La funzione di Eulero - Il piccolo teorema di Fermat - Il cifrario RSA

Enunciato

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.


Dimostrazione

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$.


Esempi

Consideriamo i seguenti esempi:

Aritmetica modulo 6Aritmetica modulo 8Aritmetica 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.

Conseguenze

Il teorema permette di calcolare l'inverso di un numero in un aritmetica finita.


Fonti bibliografiche e collegamenti

Valido HTML 4.01!