Exercise 4.3

Proof. Suppose that $a$ is a primitive root modulo $p^n$. Then $\bar{a}$ is a generator of $U(\mathbb{Z}∕p^n\mathbb{Z})$.

If $a$ was not a primitive root modulo $p$, $\bar{a}$ is not a generator of $U(\mathbb{Z}∕\mathit{p\mathbb{Z}})$, so there exists $b\in \mathbb{Z},b\wedge p=1$ such that $a^k\not\equiv b(\mathit{mod}p)$ for all $k\in \mathbb{Z}$. A fortiori $a^k\not\equiv b(\mathit{mod}{p}^n)$, and $b\wedge p^n=1$, so $\bar{b}\in U(\mathbb{Z}∕p^n\mathbb{Z})$ and $\bar{b}\notin ⟨\bar{a}⟩$ in $U(\mathbb{Z}∕p^n\mathbb{Z})$, in contradiction with the hypothesis. So $a$ is a primitive root modulo $p$.

(The reasoning on the orders of $a$, modulo $p$ and modulo $p^n$, is possible, but not so easy.) □