Proving that there are n Equivalence Classes Modulo n

Question

For $a,b,n \in \mathbb{Z}$ and $n \geq 2$, I want to prove that there are $n$ equivalence classes mod $n$. I'm not sure how to do it - would I do it inductively? Any help would be appreciated.

Answer 1

There are certainly at least $n$ equivalence classes: Namely, $[0], [1], [2], ..., [n - 1]$. To prove these are distinct, note that if $0 \le k, l < n$, then

$$[k] = [l] \implies n | l - k \implies l - k = 0$$

To see that there are at most $n$ equivalence classes, note that for any integer $m$, we may write $m = nq + r$ with $0 \le r < n$ by the division algorithm, so that $[m] = [r]$ and the class is already on our list.