Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p \equiv 1 \pmod 4$.

I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.


We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.

If $p\equiv 3\pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-g\equiv -g\pmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.

Conversely, let $p\equiv 1\pmod{4}$. We show that $-g$ is a primitive root of $p$.

By Fermat's Theorem, $g\equiv g^p\equiv -(-g)^p\pmod{p}$. But $-1$ is a QR of $p$, so $-1\equiv g^{2k}\equiv (-g)^{2k}\pmod{p}$ for some integer $k$.

t follows that $g\equiv (-g)^{2k}(-g)^p\pmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,\dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.

Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.

  • $\begingroup$ Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas $\endgroup$ – user2214 Apr 11 '15 at 20:13
  • 1
    $\begingroup$ Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$. $\endgroup$ – André Nicolas Apr 11 '15 at 22:34

$$-g=g(-1)\equiv g^{1+(p-1)/2}\equiv g^{(p+1)/2}$$

We know, ord$_ma=d, $ord$_m(a^k)=\dfrac d{(d,k)}$ (Proof @Page$\#95$)

ord$_p g^{(p+1)/2}=\dfrac{p-1}{\left(p-1,\dfrac{p+1}2\right)}$

Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2\cdot\dfrac{p+1}2=2$

As for odd prime $p,p-1$ is even

$\left(p-1,\dfrac{p+1}2\right)=2$ if $\dfrac{p+1}2$ is even $=2k$(say) $\iff p=4k-1\equiv-1\pmod4$

$\left(p-1,\dfrac{p+1}2\right)=1$ if $\dfrac{p+1}2$ is odd $=2k+1$(say) $\iff p=4k+1\equiv1\pmod4$


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.