## 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.

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

Hi,

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!