Compute the number of units in ZZ/(n)

Prove that the number of elements of (\mathbb{Z}/(n))^\times is \varphi(n), where \varphi denotes the Euler totient function.

By a previous theorem, the distinct elements of \mathbb{Z}/(n) are precisely the classes \overline{0}, \overline{1}, \ldots, \overline{n-1}. Recall that (\mathbb{Z}/(n))^\times consists precisely of those residue classes \overline{a} such that there exists \overline{b} with \overline{a} \overline{b} = \overline{1}. If 0 \leq k < n and \overline{k} \in (\mathbb{Z}/(n))^\times, we have b such that kb = qn + 1, and thus kb -qn = 1. In particular, k and n are relatively prime. Conversely, if k and n are relatively prime, then there exist a and b such that ak + bn = 1, and thus \overline{a} \overline{k} = \overline{1}. Hence, the elements of (\mathbb{Z}/(n))^\times are precisely those residue classes whose representatives in the (integer) range [0,n) are relatively prime to n. By definition, there are \varphi(n) of these.

Post a comment or leave a trackback: Trackback URL.


  • rip  On January 30, 2011 at 12:48 pm


    Am I missing something here?

    It seems to me that we don’t yet know that the subset of units of Z/(n) is equal to the subset of relatively prime representatives. In fact, you will prove that equality in a few more exercises.

    BTW, this is a wonderful resource for someone like me: I don’t have access to any academic help, but I need some help getting thru all this stuff. Thanks.

    • nbloomf  On January 30, 2011 at 10:00 pm

      The definition given by D&F for (\mathbb{Z}/(n))^\times is those classes \overline{a} for which there exists a class \overline{b} such that \overline{a} \cdot \overline{b} = \overline{1}. Combined with Bezout’s identity, this is equivalent to having a and n be relatively prime.

      This is one of the places where I would have ordered the exercises in D&F differently. I’m not sure how one would go about proving that |(\mathbb{Z}/(n))^\times| = \varphi(n) without using the “relatively prime” characterization of the elements in (\mathbb{Z}/(n))^\times.

      I’m glad you find this useful!

Leave a Reply

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

You are commenting using your 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: