Assuming $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$.

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.

• 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 – user2214 Apr 11 '15 at 20:13
• 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$. – 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$$