1
$\begingroup$

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

$\endgroup$
1

2 Answers 2

2
$\begingroup$

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

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .