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

In un'aritmetica finita di modulo N, con N numero primo, si osserva un fatto curioso relativamente alle potenze con esponente N - 1; consideriamo i seguenti esempi.
Aritmetica modulo 3Aritmetica modulo 5Aritmetica modulo 7
0^2 = 0
1^2 = 1 
2^2 = 1 [ 4 mod 3 = 1]
0^4 = 0
1^4 = 1 
2^4 = 1 [ 16 mod 5 = 1]
3^4 = 1 [ 81 mod 5 = 1]
4^4 = 1 [256 mod 5 = 1]
0^6 = 0
1^6 = 1 
2^6 = 1 [   64 mod 7 = 1]
3^6 = 1 [  729 mod 7 = 1]
4^6 = 1 [ 4096 mod 7 = 1]
5^6 = 1 [15625 mod 7 = 1]
6^6 = 1 [46656 mod 7 = 1]

Salta agli occhi che tutte le potenze con base > 0 e con esponente N - 1 valgono 1!!
Pierre de Fermat generalizzò questi esempi nel 1679 in quello che è noto come il piccolo teorema di Fermat.

Enunciato

In un'aritmetica finita di ordine N con N primo è sempre per ogni x > 0 (e ovviamente < N).
       xN - 1 = 1 mod N

Conseguenze

Il piccolo teorema di Fermat fu dimostrato da Eulero nel 1736 che lo generalizzò nel teorema di Fermat-Eulero.


Valido HTML 4.01!

Fonti bibliografiche e collegamenti