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 :(


  • 1
    $\begingroup$ 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}$? $\endgroup$ – Greg Martin Nov 14 '16 at 7:56
  • $\begingroup$ 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.). $\endgroup$ – 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$


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.