Assume that $r$ is a primitive root of the odd prime $p$ and $(r+tp)^{p-1} \not\equiv 1 (\mod p^2)$. show that $r+tp$ is a primitive root of $p^k$ for each $k \geq 1$.
How to check whether something is a primitive root??
I read a solution that is written by a stranger. he or she first said that since $r+rp\equiv r (\mod p)$, $r$ is a primitive root of $p$. is it true...? I dont understand primitive root :(
thanks
This is a duplicate but I'll write the proof again :
$\phi(p^2) = p(p-1)$ and for any $a \in \mathbb{Z}_k^\times$, $a^{\phi(k)}\equiv 1 \bmod k$ i.e. $\ \text{order}_{\bmod k}(a) \ | \ \phi(k)$.
Let $a = r+tp$ and $n = \text{order}_{\bmod p^2}(a) $.
$a^{p-1} \not\equiv 1 \bmod p^2$ means that $n \nmid p-1$, and $\frac{\phi(p^2)}{p-1} = p$ is prime so that $p \ | \ n$
Also $a^n \equiv 1 \bmod p^2 \implies a^n \equiv 1 \bmod p$ so that $ \text{order}_{\bmod p}(a)\ | \ n$.
But $a \equiv r \bmod p$ and $r$ is a primitive root $\bmod p$ i.e. $\text{order}_{\bmod m}(a) = \text{order}_{\bmod m}(r) = p-1$, so that $p-1 \ | \ n$
Altogether $p(p-1) \ | \ n$ so that $a=\phi(p^2)$ and $a$ is a primitive root $\bmod p^2$