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Φ(N) = 1 (mod N)

o anche

mΦ(N) - 1 = 0 (mod N)

Se poi N è primo allora Φ(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 ZN che ha ordine Φ(N). Per il corollario del teorema di Lagrange l'ordine di m è allora un divisore di Φ(N) e quindi mord(m) = 1 (mod N) e a maggior ragione mΦ(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!