# Understanding a proof that $U(\mathbb Z/p^l\mathbb Z)$ is cyclic.

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?)

• Confusion $2$ is clear to me now.
– Koro
Feb 20 at 8:14

"Confusion 1: Why does it matter that $$g^{p-1}\not\equiv1(p^2)?$$ Where is it used later on in the proof?"
It is used in the claim "$$g^{p-1}=1+ap,$$ where $$p\not|a$$", which is necessary to apply "Corollary 2 to Lemma 3".
First, there is a misprint in the definition of $$n'.$$ It should be $$n=p^{l-1}n'.$$ This way, the first equality $$g^n = (g^{p^{l-1}})^{n'}$$ becomes clear. The less obvious $$(g^{p^{l-1}})^{n'}\equiv g^{n'}\bmod p$$ is due to Fermat's little theorem: $$g^p\equiv g\bmod p.$$