Exercise 0.3.10 ($|(\mathbb{Z}/n\mathbb{Z})^\times| = \varphi(n)$)

Proof. If $n=1$, then $\mathbb{Z}∕\mathit{𝑛\mathbb{Z}}=\mathbb{Z}∕1\mathbb{Z}=\{\bar{1}\}$, and ${(\mathbb{Z}∕1\mathbb{Z})}^{\times }=\{\bar{1}\}$, so $\phi (1)=1=|{(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }|$. We may assume now that $n>1$.

We first prove that for all $k\in \mathbb{Z}$,

• If $\bar{k}\in {(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }$, then there is some class $\bar{l}$, where $l\in \mathbb{Z}$, such that $\bar{k}\bar{l}=\bar{1}$, therefore $\mathit{𝑘𝑙}-1=\mathit{𝑞𝑛}$ for some integer $q$. The Bézout’s relation $\mathit{𝑘𝑙}-\mathit{𝑞𝑛}=1$ shows that $k\wedge n=1$ (If $a\mid k$ and $a\mid n$, then $a\mid \mathit{𝑘𝑙}-\mathit{𝑞𝑛}=1$).
• Conversely, if $k\wedge n=1$, the Bézout’s Theorem shows that there are integers $u$ and $v$ such that $\mathit{𝑢𝑘}+\mathit{𝑣𝑛}=1$. Therefore $\mathit{𝑢𝑘}\equiv 1(\mathit{𝑚𝑜𝑑}n)$, thus $\bar{u}\bar{k}=\bar{1}$, so $\bar{k}\in {(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }$

So (1) is proven.

Consider the map

• $\psi$ is correctly defined, because by the equivalence (1), if $k\wedge n=1$, then $\bar{k}\in {(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }$.
• $\psi$ is surjective: If $c\in {(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }$, then by Exercise 2, there is some $k\in [[0,n[[$ such that $\bar{k}=c$ ,and by the equivalence (1), $k\wedge n=1$, so $\psi (k)=c$.
• $\psi$ is injective. If $\psi (i)=\psi (j)$, then $\bar{i}=\bar{j}$, where $0\le i<n$ and $0\le j<n$. By Exercise 2, $i=j$.

So $\psi$ is a bijection, and

(Since $n>1$, $n\wedge n=n\ne 1$, and $0\wedge n=n\ne 1$, so

has cardinality $\phi (n)$ by definition.)

The number of elements of ${(\mathbb{Z}∕\mathit{𝑛\mathbb{Z}})}^{\times }$ is $\phi (n)$. □