# When g and -g are both primitive roots

The question states:

Let $$g$$ by a primitive root of the odd prime $$p$$. Show that $$-g$$ is a primitive root , or not, according as $$p \equiv 1 \pmod 4$$ or not.

For me, I cannot see any connection between the type of primes and the primitive root. Any Hint is highly appreciated.

Thanks

Hint: $$-g$$ is a primitive root iff $$-g = g^k$$ with $$\gcd(k,p-1)=1$$. Connect this with the key fact:

$$-1$$ is a square mod $$p$$ iff $$p \equiv 1 \bmod 4$$

Partial solution:

If $$-g$$ is a primitive root, then $$-g \equiv g^k$$ with $$\gcd(k,p-1)=1$$ and so $$-1 \equiv g^{k-1}$$. Now $$k$$ is odd because $$\gcd(k,p-1)=1$$. Therefore, $$k-1$$ is even and $$-1$$ is a square mod $$p$$. Write $$-1 \equiv a^2$$. Then $$a$$ has order $$4$$ mod $$p$$ and so $$4$$ divides $$p-1$$, that is $$p \equiv 1 \bmod 4$$.

• Another hint: is $u$ and $v$ are squares, so is $uv$. – JavaMan Nov 23 '18 at 22:48
• It seems that I am way beyond understanding even these hints. I will make a review to the topic then come back. Please be available next time :). – Maged Saeed Nov 24 '18 at 20:51
• Hi @lhf. How $a$ has an order of 4? – Maged Saeed Dec 5 '18 at 16:32
• @MagedSaeed, $a \ne1, a^2=-1\ne1, a^4=1$. – lhf Dec 5 '18 at 17:01
• Hi @lhf. Please, consider reading my proof in the answer I have posted to this question. Many Thanks. – Maged Saeed Dec 7 '18 at 16:18

I have came up with this proof after a discussion with a friend of mine. The proof does not use anything from quadratic residue.

First of all, consider this fact:

If $$a$$ is of order $$h$$ $$\pmod n$$, then $$a^k$$ is of order $$\frac{h}{\gcd(h,k)} \quad \quad \quad\quad \quad (1)$$

The Proof:

Since $$g$$ is a primitive root, $$-1 \equiv g^{\frac{p-1}{2}} \pmod p$$. Therefore, $$-g \equiv (-1)(g) \equiv g^{\frac{p-1}{2}}g \equiv g^{\frac{p+1}{2}} \pmod p$$. Now, the order of $$g^{\frac{p+1}{2}} \pmod p$$ according to $$(1)$$ is $$\frac{p-1}{\gcd(\frac{p+1}{2},p-1)}$$. If $$p\equiv 1 \pmod 4$$, then $$\frac{p+1}{2}$$ is odd and $${\gcd(\frac{p+1}{2},p-1)}$$ is 1 making the order of $$-g$$ to be $$p-1$$. i.e. a primitive root. Otherwise, the term $$\frac{p+1}{2}$$ is even and $${\gcd(\frac{p+1}{2},p-1)} > 1$$. Therefore, the order of $$-g$$ is not $$p-1$$. i.e. not a primitive root.