Maths WorkshopMaths problems with full solutions
Exercise 224Number theory › CongruencesHigh schoolAdded 3 Nov 2026

Congruence as an equivalence relation

#equivalence relation#congruence#residue classes

Statement

Show that a≡b(modn)a\equiv b\pmod n iff n∣a−bn\mid a-b, and that this is an equivalence relation.

Hint

Check reflexivity, symmetry, transitivity.

Show solutionHide solution

Solution

Definition. a≡b(modn)  ⟺  n∣a−b  ⟺  ∃k∈Z:a=b+kna\equiv b\pmod n\iff n\mid a-b\iff\exists k\in\mathbb{Z}:a=b+kn.

Reflexive. a−a=0=n⋅0a-a=0=n\cdot0.

Symmetric. If a−b=kna-b=kn, then b−a=(−k)nb-a=(-k)n.

Transitive. If a−b=kna-b=kn and b−c=ℓnb-c=\ell n, then a−c=(k+ℓ)na-c=(k+\ell)n.

Conclusion. Congruence is an equivalence relation whose classes are the residue classes mod nn.