La congruenza modulo n è una relazione di equivalenza

Testo

Fissato $n \in \mathbb{Z}^+$, per $a,b \in \mathbb{Z}$ si pone $a \equiv b \pmod{n}$ se $n \mid (a-b)$. Dimostra che $\equiv \pmod n$ è una relazione di equivalenza su $\mathbb{Z}$.

Soluzione

Verifichiamo le tre proprietà.

• Riflessiva: $a - a = 0 = n \cdot 0$, quindi $n \mid (a-a)$ e $a \equiv a$.
• Simmetrica: se $n \mid (a-b)$, allora $a - b = nk$; dunque $b - a = n(-k)$, cioè $n \mid (b-a)$ e $b \equiv a$.
• Transitiva: se $n \mid (a-b)$ e $n \mid (b-c)$, allora $a-b = nk$ e $b-c = nh$; sommando, $a - c = n(k+h)$, quindi $n \mid (a-c)$ e $a \equiv c$.

Le tre proprietà valgono, quindi $\equiv \pmod n$ è una relazione di equivalenza. $\blacksquare$

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Congruenza · Relazione di equivalenza
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione