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$ $$ \begin{equation} \label{notone} \tag{1} g^{p^{\beta}(p-1)} \not\equiv 1 \pmod {p^{\alpha}}. \end{equation} $$

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.