Aritmetica modulare

In questo post introduciamo un “linguaggio” estremamente utile nella teoria dei numeri ed in particolare nello studio dei numeri primi. Consideriamo l’insieme dei numeri interi. Vogliamo in qualche modo “restringerlo” per concentrarci su insiemi più piccoli. Vogliamo cioè accomunare un po’ di numeri interi che hanno una qualche particolarità in comune. Ci sono tanti modi per fare questo. Il più utile e semplice da considerare, dato un intero n, è dato dalle classi di resto modulo n. Ovvero ci concentriamo sull’insieme di tutti i possibili resti della divisione di un intero per n. Questo insieme che si indica con Z_n sarà composto da n elementi: 0, 1, 2,…,n-2,n-1. Tutti i numeri interi vengono così ristretti a n numeri, nel senso che ogni numero intero m corrisponderà al resto della divisione di m per n che si indica con la scrittura m mod n (m modulo n è appunto l’operazione che prende come risultato il resto della divisione di m per n).

Esempio. Consideriamo Z_7, i suoi elementi sono i numeri 0, 1, 2, 3, 4, 5, 6. Infatti dividendo un numero qualunque per 7 abbiamo uno di questi resti. 14 mod 7 = 0, 23 mod 7 = 2, 9 mod 7=2, 13 mod 7 = 6, 49 mod 7 =0, -2 mod 7 = 5, 12 mod 7 = 5, ecc… Tutti i numeri interi possono essere identificati in Z_7 con uno tra 0, 1, 2, 3, 4, 5, 6 semplicemente attribuendogli come valore il risultato dell’operazione modulo 7.

Come visto nell’esempio, alcuni numeri hanno lo stesso resto nella divisione per un certo intero n e quindi sono “rappresentati” in Z_n dallo stesso numero. Due numeri interi a, b che hanno lo stesso risultato nell’operazione modulo n si dicono congrui modulo n e si scrive: Vuol dire che a mod n = b mod n, che si può dire in altre maniere equivalenti, per esempio a congruo b modulo n vuol dire che n divide a-b, oppure a=b+kn per qualche intero k. Per ulteriori informazioni e motivazioni potete guardare qui e qui.

Introduciamo ancora una funzione molto importante in teoria dei numeri: la funzione di Eulero f. Dato un numero n, f(n) è il numero di interi compresi tra 1 e n-1 coprimi con n. Per esempio f(6)=2, in quanto solo 1 e 5 non hanno fattori comuni con 6, mentre 2,3 e 4 sì. Analogamente f(7)=6, f(9)=6, ecc…

Terminiamo con due teoremi fondamentali nella teoria dei numeri.

Teorema di Eulero. Dati due interi a,n coprimi tra loro, allora: Piccolo Teorema di Fermat. Dato un numero intero a e un numero primo p, allora: