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$.
Best Answer
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$$