When g and -g are both primitive roots

Question

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

Answer 1

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

Answer 2

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.