Exercise 182Logic, sets and proofs › RelationsL1Added 31 Oct 2026

Congruence is an equivalence relation

#relations#modular arithmetic

Statement

Let $n\ge2$ be an integer. For $a,b\in\mathbb{Z}$ , write $a\equiv b\pmod n$ when $n$ divides $a-b$ . Prove that $\equiv$ is an equivalence relation on $\mathbb{Z}$ , and say how many equivalence classes it has.

Hint

Check reflexivity, symmetry and transitivity, then use division with remainder.

Show solutionHide solution

Solution

Reflexive. $a-a=0$ is divisible by $n$ .

Symmetric. If $n\mid a-b$ then $n\mid b-a=-(a-b)$ .

Transitive. If $n\mid a-b$ and $n\mid b-c$ , then $n$ divides the sum $(a-b)+(b-c)=a-c$ .

Classes. Every integer $a$ can be written $a=qn+r$ with $0\le r<n$ , so $a\equiv r$ . Two different remainders $r\ne r'$ in $\{0,\dots,n-1\}$ differ by less than $n$ and are not $0$ , so they are not congruent. There are exactly $n$ classes.

Congruence is an equivalence relation

Statement

Solution

More problems in Relations