Prove that $\mathbb{Z}/ \equiv 3$ has exactly three elements.

Question

The Definition: Let $R$ be an equivalence relation on the set $A$. The set of all equivalence classes is denoted by $A/R$.

The hint I have been given: First, verify that $[5]_3$, $[7]_3$, and $[0]_3$ are three different elements of $\mathbb{Z}/ \equiv 3$. Then, verify that every $m \in \mathbb{Z}$ is in one of these sets. Then explain why those two facts imply that $[5]_3$, $[7]_3$, and $[0]_3$ are the only elements of $\mathbb{Z}/ \equiv 3$.

I am lost to how I should approach this problem or better yet how I should verify that "$[5]_3$, $[7]_3$, and $[0]_3$ are three different elements of $\mathbb{Z}/ \equiv 3$". Any help is appreciated.

Answer 1

Let's do it more generally. Prove that, when $n>0$,

$a\equiv b\pmod{n}$ if and only if the remainder of the division of $a$ and $b$ by $n$ is the same.

With this at hand, we're almost done, after noticing that, by definition, $a$ is congruent modulo $n$ to the remainder of the division of $a$ by $n$.

Since the remainders are elements in $\{0,1,2,\dots,n-1\}$ and each integer is congruent to exactly one of these, the number of equivalence classes is $n$. Note that each one of these actually appears as a remainder, namely of the division of itself by $n$.

Answer 2

$[0]_3$ and $[1]_3=[7]_3$ and $[2]_3=[5]_3$ are the only elements of $\mathbf{Z}/3\mathbf{Z}$ since $[x]_3=[x\text{ mod }3]_3$.

Answer 3

The elements of $\mathbb Z/\equiv 3$ are equivalence classes. That is, $$[k]=\{x| x\equiv k\pmod 3\}$$

As these classes are actually sets, you can prove that $[5]\neq [3]$ simply by showing that there is SOME element that is in $[5]$ (for example, $5\in[5]$) which is not in $[3]$.

To prove that the elements you list are the only elements, first show that $[5]=[2]$ and $[7]=[1]$, and then show that $[0]\cup[1]\cup[2]=\mathbb Z$.

Answer 4

Induction is the key!

Start with the inductive step:

$[0]_3,[1]_3,[2]_3$ are different classes. Now, assume that $[k]_3,[k+1]_3,[k+2]_3$ are the only classes. What can you tell me about $k+3$?