## Characterize the elements of ZZ/(n)

Prove that the distinct equivalence classes in $\mathbb{Z}/(n)$ are precisely $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$. Use the Division Algorithm.

Clearly $\overline{k} \in \mathbb{Z}/(n)$ for each $0 \leq k < n$. Now let $\overline{a} \in \mathbb{Z}/(n)$. By the Division Algorithm, we have $a = qn + r$ for some $q,r$ with $0 \leq |r| < n$. Thus $\overline{a} = \overline{qn+r} = \overline{qn} + \overline{r} = \overline{r}$.

Finally, note that the $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$ are distinct as follows. Suppose $0 \leq r_1, r_2 < n$ with $r_1 \neq r_2$ and $\overline{r_1} = \overline{r_2}$. Then $n|r_2 - r_1$, so $nk = r_2 - r_1$ for some $k$, giving $r_2 = kn + r_1$. But we also have $r_2 = 0n + r_2$, and both $|r_1|$ and $|r_2|$ are less than $n$. So by the uniqueness part of the division algorithm we have $(k,r_1) = (0,r_2)$, hence $r_1 = r_2$, a contradiction.

Thus the distinct equivalence classes in $\mathbb{Z}/(n)$ are precisely $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$. $\blacksquare$