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

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: