La relazione di congruenza modulo $n$

Consideriamo due numeri interi $a$ e $b$ e un numero naturale $n$ non nullo.

I numeri $a$ e $b$ si dicono congruenti modulo $n$ se la differenza $a-b$ è un multiplo di $n$. In tal caso si indica

$$ a \equiv b \ (\mbox{mod} \ n)$$

e si dice che $a$ è congruo a $b$ modulo $n$.

Esempi

$ 7 \equiv 5 \ (\mbox{mod}\ 2 )$ , infatti $7-5 = 2$ è un multiplo di $2$.
$ 62 \equiv 29 \ (\mbox{mod}\ 11 )$ , infatti $62-29 = 33$ è un multiplo di $11$.

Equivalentemente, i numeri $a$ e $b$ si dicono congruenti modulo $n$ se la divisione euclidea di $a$ per $n$ e $b$ per $n$ dà lo stesso resto.

Classi di congruenza

La relazione di congruenza modulo $n$ è una relazione di equivalenza, infatti gode delle seguenti proprietà:

riflessiva: $ a \equiv a \ (\mbox{mod} \ n) \quad \forall \ a \in \mathbb{Z} \ \mbox{e} \ \forall \ n \in \mathbb{N}_0 $
simmetrica: $ a \equiv b \ (\mbox{mod} \ n) \ \Longrightarrow \ b \equiv a \ (\mbox{mod} \ n) \quad \forall \ a, b \in \mathbb{Z} \ \mbox{e} \ \forall \ n \in \mathbb{N}_0 $
transitiva: $ a \equiv c \ (\mbox{mod} \ n) \ \mbox{e} \ b \equiv c \ (\mbox{mod} \ n) \ \Longrightarrow \ a \equiv b \ (\mbox{mod} \ n) \quad \forall \ a, b, c \in \mathbb{Z} \ \mbox{e} \ \forall \ n \in \mathbb{N}_0 $

Possiamo quindi definire una classe di congruenza, detta classe di congruenza di $a$ modulo $n$:

$$[a]_n = \{ b \in \mathbb{z} : b \equiv a \ (\mbox{mod} \ n) \}$$

Esempi

$[2]_3 = \{ b \in \mathbb{z} : b \equiv 2 \ (\mbox{mod} \ 3) \} = \{ 2, 5, 8, 11, 14, …\} $ , questa classe di congruenza contiene tutti i numeri interi che divisi per $3$ danno resto $2$ (che è il resto della divisione $2:3$ ).
$[14]_3 = \{ b \in \mathbb{z} : b \equiv 14 \ (\mbox{mod} \ 3) \} = \{ 2, 5, 8, 11, 14, …\} $ , questa classe di congruenza contiene tutti i numeri interi che divisi per $3$ danno resto $2$ (che è il resto della divisione $14:3$ ). Osserviamo che questa classe contiene gli stessi elementi della classe precedente, ovvero: $ [14]_3 = [2]_3 $.
$[7]_7 = \{ b \in \mathbb{z} : b \equiv 7 \ (\mbox{mod} \ 7) \} = \{ 0, 7, 14, 21, 28, …\} $ , questa classe di congruenza contiene tutti i numeri interi che divisi per $7$ danno resto $0$ (che è il resto della divisione $7:7$ ).
$[35]_7 = \{ b \in \mathbb{z} : b \equiv 35 \ (\mbox{mod} \ 7) \} = \{ 0, 7, 14, 21, 28, …\} $ , questa classe di congruenza contiene tutti i numeri interi che divisi per $7$ danno resto $0$ (che è il resto della divisione $35:7$ ). Osserviamo che questa classe contiene gli stessi elementi della classe precedente, ovvero: $ [35]_7 = [7]_7 $. Di più, possiamo individuare altre classi che contengono gli stessi elementi di queste, ad esempio: $ [0]_7 $.

Insieme quoziente

Prendendo spunto dalle osservazioni scritte per gli esempi sopra riportati, dato un numero $ n \in \mathbb{N}_0 $, possiamo concludere che il numero di classi di equivalenza distinte che possiamo considerare è $ n $. Infatti, le classi di equivalenza generate da numeri maggiori di $n-1$ corrispondono ad una delle classi precedenti.

Come per tutte le classi di congruenza, anche per la classe di congruenza di $a$ modulo $n$ possiamo definire un insieme quoziente, che contiene tutte le classi di equivalenza.

Questo insieme viene indicato con $ \mathbb{Z}_n$.

L’insieme quoziente contiene $n$ elementi.

Esempi

$ \mathbb{Z}_3 = \{ [0]_3 , [1]_3 , [2]_3 \} $
$ \mathbb{Z}_8 = \{ [0]_8 , [1]_8 , [2]_8 , [3]_8 , [4]_8, [5]_8, [6]_8, [7]_8 \} $

Gruppi definiti con la relazione di equivalenza

$ ( \mathbb{Z}_n , +) $ è un gruppo abeliano, infatti:

esiste l’elemento neutro, $ [0]_n $
per ogni elemento $ [a]_n $ esiste l’elemento inverso $ [b]_n $
l’addizione è associativa
l’addizione è commutativa

$ ( \mathbb{Z}^*_n , \cdot ) $, dove $ \mathbb{Z}^*_n $ è l’insieme degli elementi di $ \mathbb{Z}_n – [0]_n $ che hanno l’inverso rispetto alla moltiplicazione, è un gruppo abeliano, infatti:

esiste l’elemento neutro, $ [1]_n $
per ogni elemento $ [a]_n $ esiste l’elemento inverso $ [b]_n $
la moltiplicazione è associativa
la moltiplicazione è commutativa