Una relazione di equivalenza sull’insieme degli interi divide gli interi in classi di equivalenza; nel nostro caso la congruenza modulo un intero strettamente positivo m dividerà Z in classi di congruenza (modulo m).

 

Definizione. Se a è un intero, la classe di congruenza di a modulo m è definita come

[a]_m = { xÎZ / x º a (mod m) } = { xÎZ / x=a+km, con kÎZ },

cioè è l’insieme di tutti gli interi che sono congrui ad a modulo m.

 

Osservazioni. Se due classi di congruenza hanno un elemento in comune, allora coincidono.

Inoltre, ogni intero a sta in una ed una sola classe di congruenza, da cui segue che se a e b non sono congruenti modulo m, allora le loro classi di congruenza sono disgiunte.

 

In simboli, se a º b (mod m), allora

x º a (mod m) se e solo se x º b (mod m);

e se a ¹ b (mod m), allora

[a]_m Ç [b]_m = Æ,

poiché se esiste un x che appartiene all’insieme formato dall’intersezione delle loro classi di congruenza, cioè se esiste x Î [a]_m Ç [b]_m , allora  x º a (mod m) e x º b (mod m), da cui discende che a º b (mod m) per le proprietà studiate della congruenza, e questo è assurdo.

 

Possiamo nuovamente riformulare il

 

Lemma di divisione. Ogni classe di congruenza modulo m contiene uno ed un solo intero r con 0 £ r < m, dove

[a]_m = { rÎZ / a=q×m+r, con rÎZ }.

 

Una conseguenza del lemma è il seguente corollario:

Corollario. Esistono precisamente m classi di congruenza modulo m, ossia

Z_m = {[0]_m, [1]_m,..., [m-1]_m }.

 

Le classi di congruenza si possono sommare e moltiplicare, quindi sono chiuse rispetto alla somma e alla moltiplicazione con le operazioni definite come:

 

1)      [a]_m + [b]_m := [a+b]_m,

dove   +,       Z_m x Z_m  ¾® Z_m

            ([a]_m,[b]_m) ® [a+b]_m;

2)      [a]_m × [b]_m := [a× b]_m,

dove   ×,       Z_m x Z_m  ¾® Z_m

            ([a]_m,[b]_m) ® [a× b]_m.

 

dove [0]_m sarà l’elemento neutro della somma e  [1]_m sarà l’elemento neutro della moltiplicazione.

 

Le operazioni +,× sono ben definite, ossia il comportamento delle seguenti operazioni non dipende dalla scelta del valore che appartiene alla classe di congruenza, ma se scegliamo valori diversi per a e b, le classi che abbiamo definito non cambiano, cioè

 

Proposizione. Supponiamo che [a]_m = [a’]_m e [b]_m = [b’]_m, allora

[a+b]_m = [a’+b’]_m  e  [a×b]_m = [a’×b’]_m.

 

Inoltre +,× definite su Z_m godono delle stesse proprietà di +,× definite su Z, per cui valgono ancora la proprietà associativa e distributiva:

presi a=[a]_m, b=[b]_m, γ=[c]_m Î Z_m si possono facilmente dimostrare che valgono le seguenti regole di calcolo:

 

(a+b)+γ = a+(b+ γ);

(a×b) × γ = a×(b× γ);

a×(b+ γ) = a×b+a× γ;

a+0 = a;

a×0 = 0;

a×1 = a.

 

La potenza n-esima di a viene invece definita come il prodotto di n copie di a, quindi si ha che:

aⁿ = ([a]_m)ⁿ = [aⁿ]_m.

Nell’anello degli interi, gli unici valori a per cui esiste un intero b tale che ab=1 sono a=1, a=-1, mentre in Z_m si ha che:

 

Proposizione. In Z_m , data a =[a]_m, esiste un b=[x]_m tale che [a]_m×[x]_m =[1]_m se e solo se MCD(a,m)=1, cioè se e solo se a e m sono primi fra loro. Inoltre se b esiste è unico.

 

In particolare, l’elemento a  si dice invertibile, l’elemento b si dice inverso di a e si denota con a^-1.

Dimostrazione

Se p è un primo, allora ogni intero non divisibile per p è relativamente primo con p, da cui

Corollario. Se p è primo, ogni elemento di Z_p diverso da zero è invertibile.

 

La nuova formulazione del teorema di Fermat diventa:

 

Teorema di Fermat. Sia p primo. Se aÎZ_p, allora

a^p=a.

Se a¹0, abbiamo che a^p-1=1.

 

L’insieme Z_m con le operazioni di addizione e moltiplicazione è una struttura chiamata anello commutativo.

 

• Esempi

• Esercizi