# Show that $r$ is a primitive root (mod $p^k$)

Let $$p$$ be an odd prime, and let $$r$$ be a primitive root (mod $$p$$) such that $$r^{p-1} \not\equiv 1$$ (mod $$p^2$$). Show that $$r$$ is a primitive root (mod $$p^k$$) for all $$k \geq 1$$.

So I start of by computing that $$\phi(p^k)$$ $$=p^{k-1} (p-1)$$. Now, if $$r^x = 1$$ (mod $$p^k$$) then $$r^x = 1$$ (mod $$p$$), and since $$r^{p-1} = 1$$ (mod $$p$$), we get that $$(p-1) | x$$ from basic properties of the order of a integer. The order of $$r$$ (mod $$p^k$$) must hence be on the form $$p^j (p-1)$$, $$j < k$$.

I need help to prove that $$j = k-1$$.

Lemma: $a\in\mathbb Z$ is a primitive root mod $n\ge 2$ if and only if $\gcd(a,n)=1$ and $$q\mid \phi(n)\implies a^{\phi(n)/q}\not\equiv 1\pmod{n}$$

(here $q$ is prime). In your case, you're given that $p$ is an odd prime, $r$ is a primitive root mod $p$ and $r^{p-1}\not\equiv 1\pmod{p^2}$.

I.e. you're given that $p$ is an odd prime, $\gcd(r,p)=1$ and $q\mid p-1\implies r^{(p-1)/q}\not\equiv 1\pmod{p}$ and $r^{p-1}\not\equiv 1\pmod{p^2}$.

You want to prove that if $k\ge 2$, then $\gcd\left(r,p^k\right)=1$ and $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$ and $r^{p^{k-1}(p-1)/q}\not\equiv 1\pmod{p^k}$ for all prime divisors $q$ of $p-1$.

$\gcd\left(r,p^k\right)=1$ is clear, because $\gcd(r,p)=1$.

$r^{p^{k-1}(p-1)/q}\not\equiv 1\pmod{p^k}$ is clear, because if $r^{p^{k-1}(p-1)/q}\equiv 1\pmod{p}$, then, since $r$ is a primitive root mod $p$, we get $p-1\mid p^{k-1}(p-1)/q\iff p-1\mid (p-1)/q$ (because $\gcd(p-1,p^{k-1})=1$; see Euclid's Lemma), contradiction.

In order to prove $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$, we'll use induction. If $k=2$, then it's true (because it's given that $r^{p-1}\not\equiv 1\pmod{p^2}$). If it's true for some $k\ge 2$, then we'll prove it's true for $k+1$.

I.e., if $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$ for some $k\ge 2$, then we'll prove $r^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$.

We can prove the contrapositive. I.e., if $r^{p^{k-1}(p-1)}\equiv 1\pmod{p^{k+1}}$ for some $k\ge 2$, then $r^{p^{k-2}(p-1)}\equiv 1\pmod{p^k}$.

Let $r^{p^{k-2}(p-1)}=a$. Then you want to prove that if $k\ge 2$, then $$a^p\equiv 1\pmod{p^{k+1}}\implies a\equiv 1\pmod{p^k}$$

There are two ways to prove this:

$1)\$ Remember $a^p-1=(a-1)\left(a^{p-1}+a^{p-2}+\cdots+1\right)$.

By Fermat's Little theorem $a\equiv 1\pmod{p}$. Let $a=pk+1$. Then it's enough to prove that $$p^2\nmid a^{p-1}+a^{p-2}+\cdots+1$$

$$=(pk+1)^{p-1}+(pk+1)^{p-2}+\cdots+1$$

Use the Binomial theorem:

$$\equiv ((p-1)pk+1)+((p-2)pk+1)+\cdots+((p-p)pk+1)\pmod{p^2}$$

$$\equiv (-pk-2pk-\cdots-ppk)+p\equiv p\left(\frac{-kp(p+1)}{2}+1\right)\equiv p\not\equiv 0\pmod{p^2}$$ $2)\$ By Fermat's Little theorem $a\equiv 1\not\equiv 0\pmod{p}$, so by Lifting The Exponent Lemma (LTE): $$\upsilon_p\left(a^p-1\right)=\upsilon_p(a-1)+\upsilon_p(p)=\upsilon_p(a-1)+1$$

$$\upsilon_p\left(a^p-1\right)\ge k+1\iff \upsilon_p(a-1)\ge k$$