# Determine if a number is a primitive root

Let $p$ be an odd prime, let $g$ be a primitive root of $p$. Prove $-g$ is a primitive root of $p$ if and only if $$p\equiv1\pmod{4}$$ Hint: express $-g$ as $g^{k}$, then use property 6 ... verify $$gcd((p+1)/2,p-1) = gcd((p-1)/2,((p-1)/2)-1)$$ Unfortunately I am not entirely sure what property 6 is, but I believe it is: "If $g$ is a primitive root of $p$, then $g^k$ is a primitive root of $p$ if and only if $gcd(ϕ(p),k)=1$
Can anyone confirm that this is the property I need for this proof?
So far I have:
Let $g$ be a primitive root of an odd prime $p$. Because $g$ is a primitive root all other equivalence classes $mod(p)$ can be expressed as a power of $g$. Therefore there is some integer $k$ such that $-g\equiv g^k$.

From here I'm not sure how to continue or even what the rest of the hint is suggesting.

• Who gave that hint? How come you're not sure what "property 6" is?? – DonAntonio Mar 7 '18 at 9:39
• My professor gave the hint. I'm not sure what property 6 is because he doesn't specify what properties he's referring to, and I can't find a list of 6+ properties in my notes or on any of the handouts i have. I messaged a classmate, but he never responded so that leaves me in a bit of a pickle – JakeRyan34 Mar 7 '18 at 9:46
• What about asking your prof. ...?? Could it be that $\;-1\;$ is a quadratic residue modulo a prime $\;p\;$ iff $\;p=-1\pmod 4\;$ ?\ – DonAntonio Mar 7 '18 at 9:51
• Well it's 4am here so I don't imagine he would be very responsive lol If I can't figure this out I plan to ask him in the morning – JakeRyan34 Mar 7 '18 at 9:53
• Yes, do that.... – DonAntonio Mar 7 '18 at 9:54

## 2 Answers

Suppose $g$ is a primitive root, then $$g^{p-1}\equiv_p1\iff (g^{\frac{p-1}{2}}-1)(g^{\frac{p-1}{2}}+1)\equiv_p 0$$ Since $g$ is a primitive root $g^{\frac{p-1}{2}}\not\equiv_p 1$, we must have $$g^{\frac{p-1}{2}}\equiv_p -1$$

Therefore $(-1)^{\frac{p-1}{2}}g^{\frac{p-1}{2}}\equiv_p (-g)^{\frac{p-1}{2}}\equiv_p (-1)^{\frac{p+1}{2}}$, so $-g$ is a primitive root $\iff p\equiv_4 1$.

• $p \equiv 1 mod(4)$ implies that $\frac{p-1}2$ is even right? – JakeRyan34 Mar 7 '18 at 14:18
• That's right. But it also implies that $(-g)^{\frac{p-1}{2}}\equiv_p -1$, which means that $-g$ is a primitive root. – cansomeonehelpmeout Mar 7 '18 at 14:20
• Wouldn't that mean that $(-1)^\frac{p-1}2 = 1$ since $\frac{p-1}2$ is even? – JakeRyan34 Mar 7 '18 at 15:09
• Do you agree that $(-1)^2 3^2=(-3)^2$? That's the same idea. – cansomeonehelpmeout Mar 7 '18 at 15:39
• ohhh i see what you mean, thanks – JakeRyan34 Mar 7 '18 at 15:51

More generally ord$_pa=d\implies$ ord $_p(a^k)=\dfrac d{(k,d)}$ (Proof @Page#95)

$$\displaystyle -g\equiv g^{\frac{p-1}2+1}\pmod p$$

Now if $d$ divides both $\dfrac{p+1}2, p-1$

$d$ must divide $2\cdot\dfrac{p+1}2-(p-1)=2$

$\implies\left(\dfrac{p+1}2, p-1\right)=1$ iff $\dfrac{p+1}2$ is odd as $p-1$ is even

$\dfrac{p+1}2=2n+1$(say)$\implies p=4n+1\equiv1\pmod4$

• do you mean g^(((p-1)/2))+1) or g^((p-1)/2)+1? The formatting on this site is hard to deal with lol – JakeRyan34 Mar 7 '18 at 10:09
• @JakeRyan34, Have you understood uptil then? – lab bhattacharjee Mar 7 '18 at 10:12
• I think so. I'm working my way through that other thread and comparing it to this problem. – JakeRyan34 Mar 7 '18 at 10:17
• @JakeRyan34, The exponent is $$1+\dfrac{(p-1)}2$$ – lab bhattacharjee Mar 7 '18 at 10:17
• In that case I don't understand haha. Whose answer should I be looking at on that thread? – JakeRyan34 Mar 7 '18 at 10:20