Let $k ∈ N0$ be a fixed non-negative integer.

Question

We define the relation $∼k$ on $Z$ by declaring that if $m, n ∈ Z$ then $m$ $∼k$ $n$ if and only if $m − n$ is divisible by $k$.

Show that $∼k$ defines an equivalence relation on $Z$.

Show that the number of equivalence classes of $Z/∼k$ is given by:

$|Z/∼k|$={$k$, if $k ≥ 1$ and $∞$, if $k = 0$}

Answer 1

You have to verify that it satisfies the definition of an equivalence relation:

1) It's reflexive because $m \sim m$ as $m-m$ is divisible by any $k$.

2) It's symmetric because if $m \sim n$ this implies $m-n$ is divisible by $k$, but then so is $n-m$.

3) It's transitive (this is usually the most challenging to prove) because if $m \sim n$ and $n \sim p$ then $m-p = (m-n) + (n-p)$. Both terms on the right are divisible by $k$ so $m-p$ is as well.

This implies $\sim$ is an equivalence relation.

To prove the final statement, it's clear that if $k = 0$ nothing is divisible by $0$, so you get infinity.

Otherwise you get $\mathbb{Z}/k\mathbb{Z}$. You are precisely equating two elements if $n \equiv m \pmod k$. The equivalence classes are exactly all of the residue classes, i.e. the remainders of the numbers on division by $k$. $|\mathbb{Z}/k\mathbb{Z}| = k$.

Answer 2

Hint: $\dfrac{\mathbb{Z}}{\sim k} = \mathbb{Z}_k = \lbrace \overline{0}, \overline{1}, \ldots, \overline{k-1}\rbrace$, where $\overline{a}=\lbrace a+nk, n\in\mathbb{Z}\rbrace$.