Exercise 455Number theory › Divisibility and gcdL1Added 3 Nov 2026

Congruence classes modulo $n$

#congruences#residue classes#partition

Statement

Show that congruence modulo $n$ partitions $\mathbb{Z}$ into $n$ classes, and compute the classes for $n=4$ .

Hint

$a\equiv b\pmod n\iff n\mid a-b$ is an equivalence relation.

Show solutionHide solution

Solution

Equivalence relation. Reflexive: $n\mid0$ . Symmetric: $n\mid a-b\Rightarrow n\mid b-a$ . Transitive: $n\mid a-b$ and $n\mid b-c\Rightarrow n\mid a-c$ .

Classes. The class of $a$ is $\{a+kn:k\in\mathbb{Z}\}$ , determined by the remainder of $a$ mod $n$ .

For $n=4$ : classes are $\bar0,\bar1,\bar2,\bar3$ , represented by the residues $0,1,2,3$ .

Conclusion. $\mathbb{Z}/n\mathbb{Z}$ has $n$ elements.

Congruence classes modulo $n$

Statement

Solution

More problems in Divisibility and gcd