ARITMETICA MODULARE

Consideriamo i numeri interi Z. Si dice che due numeri interi a,b sono congrui modulo n e si scrive
a=b mod n
se a-b è un multiplo di n

Ad esempio : 4=1 mod 3 e ande 7=1 mod 3
se a=b mod n allora a e b hanno lo stesso resto se vengono divisi per n
Ad esempio i numeri che sono uguali modulo 3 sono 1 - 4 - 7 - 10
Si pone [1] mod3 per indicare l'insieme di tutti i numeri congrui a 1 mod3

In generale [a] mod n indica l'insieme di tutti i numeri interi che divisi per n hanno resto a e si dice CLASSE di a modulo n.

Fissato n le sue classi sono n : [0], [1], [2]....[n-1]
La congruenza è una relazione di equivalenza e l'unione delle classi (che sono disgiunte) è tutto l'insieme Z degli interi.

Nell'insieme delle classi mod n si può definire l'operazione di somma e prodotto. Risulta:
[a]+[b]=[a+b]
[a][b]=[ab] 

APPLICAZIONI:
Se siamo nell'aritmetica modulo 7
[10]=[3]
[100]=[10][10] =[9]=[2]
[1000]=[10][100]=[3][2]=[6]
Quanto vale il resto di 1546 per 7? E' divisibile per 7?
allora [1546]=[1000]+5[100]+4[10]+6=[6]+5[2]+4[3]+6=[6]+[3]+[5]+[6]=[20]=[6]
è 6
quindi 1540 è divisibile per 7!

L'aritmetica dell'orologio è modulo 12 se consideriamo la lancetta delle ore.
[1]=[13] mod 12
 Se sono le 14 e passano 13 ore allora la lancetta segnerà le 3: [14]+[13]=[27]=[3]