# Show that $−g$ is also a primitive root of $p$ if $p\equiv 1 \pmod{4}$, but that $ord_p(−g) = \frac{p−1}{2}$ if $p \equiv 3 \pmod{4}$. [duplicate]

This question already has an answer here:

Let $$p$$ be an odd prime and let $$g$$ be a primitive root $$\pmod{p}$$. Show that $$−g$$ is also a primitive root of $$p$$ if $$p \equiv 1 \pmod{4}$$, but that $$ord_p(−g) = \frac{p−1}{2}$$ if $$p \equiv 3 \pmod{4}$$.

So far, I have shown as $$p \equiv1 \pmod{4}$$ I can use Fermat's Little Theorem. $$g \equiv g^{p} \equiv -(-g)^{p} \pmod{p}$$

Since $$p \equiv 1 \pmod{4}$$, $$x^2 \equiv -1 \pmod{p}$$. ($$-1$$ is a QR of $$p$$) There $$\exists k \in \mathbb{Z}$$ such that

$$-1 \equiv g^{2k} \equiv (-g)^{2k} \pmod{p}$$

Thus, $$g \equiv (-g)^{2k}(-g)^{p} \pmod{p}$$. As $$g$$ is congruent to $$-g^{p}$$, $$-g$$ is a primitive root of $$p$$.

Is this enough to show the first part of the question, also how do I begin to show the 2nd part?

## marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos SantosDec 13 '18 at 15:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• math.stackexchange.com/questions/1229270/… – lab bhattacharjee Dec 11 '18 at 11:43
• Find a way to write -1 as a power of the primitive root g then use the fact that $\text{ord}_p(g^d) = \frac{\text{ord}_p(g)}{\text{gcd}(\text{ord}_p(g),d)}$. That is, find the gcd$(\text{ord}_p(g),d)$, where $-g \equiv g^d \text{mod }p$ and the result will follow. – user337254 Dec 11 '18 at 15:28

## 1 Answer

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)} = \frac{p-1}{2} > 1$$. Therefore, the order of $$-g$$ is not $$p-1$$. i.e. not a primitive root.

I am quoting my answer on my question here with some minor changes.