Congruence modulo n is an equivalence relation

Statement

Fix $n \in \mathbb{Z}^+$; for $a,b \in \mathbb{Z}$ set $a \equiv b \pmod{n}$ if $n \mid (a-b)$. Prove that $\equiv \pmod n$ is an equivalence relation on $\mathbb{Z}$.

Solution

We check the three properties.

• Reflexive: $a - a = 0 = n \cdot 0$, so $n \mid (a-a)$ and $a \equiv a$.
• Symmetric: if $n \mid (a-b)$, then $a - b = nk$; hence $b - a = n(-k)$, i.e. $n \mid (b-a)$ and $b \equiv a$.
• Transitive: if $n \mid (a-b)$ and $n \mid (b-c)$, then $a-b = nk$ and $b-c = nh$; adding, $a - c = n(k+h)$, so $n \mid (a-c)$ and $a \equiv c$.

All three properties hold, so $\equiv \pmod n$ is an equivalence relation. $\blacksquare$