Exercise 3.7

Proof. The proof is more clear if we stay in $\mathbb{Z}∕\mathit{n\mathbb{Z}}$.

Let $P=\underset{x\in U(\mathbb{Z}∕\mathit{n\mathbb{Z}})}{\prod <!--\; FUNCTION\; APPLICATION\; -->}x$

(if $\{a_1,\dots ,a_{\varphi (n)}\}$ is a reduced residue system modulo $n$, then $P=\underset{i=1}{\overset{\varphi (n)}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}\overline{a_i}$.)

Let $a\in \mathbb{Z}$ such that $a\wedge n=1$, then $b=\bar{a}\in U(\mathbb{Z}∕\mathit{n\mathbb{Z}})$. We define

$\text{∙}$ Then $\psi (x)=\psi (x^{\prime })\Rightarrow \mathit{bx}=b{x}^{\prime }\Rightarrow b^{-1}\mathit{bx}=b^{-1}b{x}^{\prime }\Rightarrow x=x^{\prime }$, so $\psi$ is injective.

$\text{∙}$ Let $y\in U(\mathbb{Z}∕\mathit{n\mathbb{Z}})$. If $x=b^{-1}y$, then $\psi (x)=b{b}^{-1}y=y$, so $\psi$ is surjective.

$\psi$ is a bijection, so

that is

As $y=\underset{x\in U(\mathbb{Z}∕\mathit{n\mathbb{Z}})}{\prod <!--\; FUNCTION\; APPLICATION\; -->}x$ is in the group $U(\mathbb{Z}∕\mathit{n\mathbb{Z}})$, $y$ is invertible, thus

That is ${\bar{a}}^{\varphi (n)}=1$ : for all $a\in \mathbb{Z}$, if $a\wedge n=1$, then $a^{\varphi (n)}\equiv 1(\mathit{mod}n)$. □