If $r$ is a primitive root mod $p$ and $(r+tp)^{p-1} \not \equiv 1 \pmod{p^2}$, then $r+tp$ is a primitive root mod $p^k$

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

• You need to determine the order of $r+tp$ modulo $p^k$. Start with $k=2$ for example: what do you know about the order of $r+tp$ modulo $p^2$? That is, what do you know about which exponents $n$ give you either $(r+tp)^n\equiv1\pmod{p^2}$ or $(r+tp)^n\not\equiv1\pmod{p^2}$? – Greg Martin Nov 14 '16 at 7:56
• A primitive root is all generator of the multiplicative group of classes modulo $p$. For example $3$ is a p. r. of $7$ because $\{3,3^2,3^3,3^4,3^5,3^6\}$ is equal to the set $\{1,2,3,4,5,6\}$ modulo $7$. You can verify that $5$ is also a p.r. of $7$. For $p=11$ try to verify that $2,6,7$ and $8$ are primitive roots (so you learn for ever this first notion of p.r.). – Piquito Nov 14 '16 at 10:11

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$