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

Algebra Solutions

Compute the number of units in ZZ/(n)

No comments:

Post a Comment