Algebra Solutions: 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$

Algebra Solutions

Characterize the elements of ZZ/(n)

No comments:

Post a Comment