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.



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

  • $\begingroup$ Another hint: is $u$ and $v$ are squares, so is $uv$. $\endgroup$ – JavaMan Nov 23 '18 at 22:48
  • $\begingroup$ 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 :). $\endgroup$ – Maged Saeed Nov 24 '18 at 20:51
  • $\begingroup$ Hi @lhf. How $a$ has an order of 4? $\endgroup$ – Maged Saeed Dec 5 '18 at 16:32
  • 1
    $\begingroup$ @MagedSaeed, $a \ne1, a^2=-1\ne1, a^4=1$. $\endgroup$ – lhf Dec 5 '18 at 17:01
  • $\begingroup$ Hi @lhf. Please, consider reading my proof in the answer I have posted to this question. Many Thanks. $\endgroup$ – 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.


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.