If $p$ is an odd prime, $l\in \mathbb Z^+$, then $U(\mathbb Z/p^l\mathbb Z)$ is cyclic, i.e., there exist primitive roots mod $p^l$.
Background:
Theorem $1$: $U(\mathbb Z/p\mathbb Z)$ is cyclic.
Definition: We say that $a\in \mathbb Z$ is a primitive root mod $p$ if $\bar a\in \mathbb Z/p\mathbb Z$ is a generator of $U(\mathbb Z/p\mathbb Z).$
Corollary $2$ to lemma $3$: For an odd prime $p$ and $a: p\not|a$, the order of $1+ap$ is $p^{l-1}$ mod ($p^l$).
Notations: The fact that $a\equiv b \pmod c$ will be at times denoted by $a\equiv b(c)$.
Here is a proof of it, but I don't understand some steps in it.
By Theorem 1 there exist primitive roots mod $p$. If $g\in \mathbb Z$ is a primitive root mod $p$, then so is $g + p$. If $g^{p-1} \equiv 1 (p^2)$, then $(g + p)^{p- 1} \equiv g^{p-1}+(p-1)g^{p-2}p\equiv 1+(p-1)g^{p-2}p (p^2)$. Since $p^2$ does not divide $(p - 1)g^{p-2}p$, we may assume from the beginning that g is a primitive root mod $p$ and that $g^{p - 1} \not\equiv 1 (p^2)$. (Confusion $1$: Why does it matter that $g^{p - 1} \not\equiv 1 (p^2)$? Where is it used later on in the proof?)
We claim that such a $g$ is already a primitive root mod $p^l$. To prove this it is sufficient to prove that if $g^n \equiv 1 (p^l) $, then $\phi(p^l) = p^{l-1} (p - 1)|n$. (Confusion $2$: Why is it sufficient? I think that we have to show that $g^{\phi(p^l)}\equiv 1(p^l)$, and that $g^t\not\equiv 1(p^l)$ for any $t| \phi(p^l)$)
$g^{p-1}= 1 + ap$, where $p\not| a$. By Corollary 2 to Lemma 3, $p^{l-1}$ is the order of $1 + ap$ mod $p^l$. Since $(1 + ap)^n = 1 (p^l)$ we have $p^{l-1}|n$.
Let $n = p^{i- 1}n'$. Then $\color{red}{g^n = (g^{p^{l-1}})^{n'}\equiv g^{n'} (p)}$ , and therefore $g^{n'} = 1 (p)$. Since $g$ is a primitive root mod $p$, $p - 1 |n'$. We have proved that $p^{l-1}(p - 1)|n$, as required. (Confusion $3$: How does the red colored part follow?)
Please help. Thanks.
