1
$\begingroup$

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?

$\endgroup$

marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 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.

  • 1
    $\begingroup$ math.stackexchange.com/questions/1229270/… $\endgroup$ – lab bhattacharjee Dec 11 '18 at 11:43
  • 1
    $\begingroup$ 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. $\endgroup$ – user337254 Dec 11 '18 at 15:28
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.