# How to use Hensel lemma to show that primitive root mod $p$ gives primitive root mod $p^2$ of the form $g + tp$

How to use Hensel lemma to show that primitive root mod $p$, where $p$ is prime, gives primitive root mod $p^2$ of the form $g + tp?$

I tried to start with congruence $g^{p-1} \equiv 1 \pmod p,$ so $f(g) = g^{p-1} - 1$ and $f'(g) = (p-1)g^{p-2} \ne 0.$

$f'(g)^{-1} = (p-1)^{p-2}g \pmod p,$ because $(p-1)^{p-1}g^{p-1}\equiv 1 \pmod p.$

Lemma: If $p$ is any odd prime and $g$ is a primitive root of $p^2,$ then $g$ is a primitive root of $p^k$ for all $k \ge 2.$

Proof: Let $h$ be order of $g$ modulo $p^{\alpha}.$ When $\phi(p^2)\mid h$ and $h \mid \phi(p^{\alpha}).$ Thus $h = p^{\beta}(p-1).$ To prove that $g$ is a primitive root modulo $p^{\alpha}$ we need to show that the following congruence holds for $\beta = \alpha - 2$ $$$$\label{notone} \tag{1} g^{p^{\beta}(p-1)} \not\equiv 1 \pmod {p^{\alpha}}.$$$$

By Fermat we know that $g^{p-1} \equiv 1\pmod p.$ So $g^{p-1} = 1 + b_1 p,$ where $p \not\mid b_1.$ Byt raising both sides into $p$-th power we have $g^{p(p-1)} = (1+b_1p)^p = 1 + {p \choose 1}b_1p + {p \choose 2}(b_1p)^2 + \cdots.$ As $p > 2$ we have $g^{p(p-1)} \equiv 1 + b_1p^2 \pmod {p^3}.$ Hence $\ref{notone}$ holds for $\alpha = 3.$ Now raise both sides into $p$-th power again and see that $g^{p^2(p-1)} \equiv 1 + b_2p^3 \pmod {p^4},$ this geives as $\ref{notone}$ for $\alpha = 4.$ And we can go on. $\square$

Corollary to Hensel's lemma: If $f'(x_0) ≡ 0 \pmod p,$ but $x_0$ is not a solution of $f(x) \equiv 0 \pmod {p^{k+1}},$ then $x_0$ does not lift to any solutions of $f(x) \equiv 0 \pmod {p^{k+1}}.$

Proof: To prove it observe that second term in Taylor series for $f(x)$ vanishes because $f'(x_0) \equiv 0 \pmod p.$ All next terms are also vanish.

Theorem: If $p$ is an odd prime, $k \ge 2,$ and $g$ is a primitive root of $p^k,$ then $g + tp^k$ is a primitive root of $p^{k+1}$ for all $0 \le t \le p − 1.$ Furthermore, all the primitive roots of $p^{k+1}$ can be constructed this way.

Proof: To prove this theorem we first can show that order of $g+tp^k$ is either $\phi(p^{k+1})$ or $\phi(p^k).$ Let $h = \mbox{ord}_{p^{k+1}}(g+tp^k).$ As order it must be a divisor of $\phi(p^{k+1}),$ so $xh = \phi(p^{k+1}).$ On the other hand $(g+tp^k)^h \equiv 1 \pmod {p^{k+1}}$ and so $(g+tp^k)^h \equiv 1 \pmod {p^k}.$ Thus $h = y\phi(p^k).$ And we have $$xy\phi(p^k) = \phi(p^{k+1}),$$ thus $x, y \in \{1, p\}.$ So, order of $g+tp^k$ is either $\phi(p^{k+1})$ or $\phi(p^k).$ In former case we are done, but in later case we can go on with assuming that order of $g+tp^k$ is indeed $\phi(p^k),$ this will lead us to contradiction and $\color{blue}{here\ we\ will\ need\ Hensel's\ lema.}$

So we are assuming that $(g+tp^k)$ is a solution to congruence $x^{\phi(p^k)} \equiv 1 \pmod{p^{k+1}}.$ We also know that $g$ is primitive root of $p^k,$ so $g^{\phi(p^k)} \equiv 1 \pmod {p^k}.$ So $f(x) = x^{\phi(p^k)} - 1$ and $f'(x) = \phi(p^k)x^{\phi(p^k)-1}.$ $$f'(g) = p(p^{k-1}-p^{k-2})g^{\phi(p^k)-1} \equiv 0 \pmod p.$$ Remember that $k\ge 2.$

$g$ is also a primitive root of $p^2.$ So, by the previous lemma it is also a primitive root of $p^{k+1}.$ So, $g$ is not a soln for $f(x) \equiv 1 \pmod {p^{k+1}}.$ With help of corollary to Hensel's lemma we see that we came to conradiction.$\square$

One can find part of this here Constructing the Primitive Roots of Prime Powers