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.

  • $\begingroup$ Who gave that hint? How come you're not sure what "property 6" is?? $\endgroup$ – DonAntonio Mar 7 '18 at 9:39
  • $\begingroup$ 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 $\endgroup$ – JakeRyan34 Mar 7 '18 at 9:46
  • $\begingroup$ What about asking your prof. ...?? Could it be that $\;-1\;$ is a quadratic residue modulo a prime $\;p\;$ iff $\;p=-1\pmod 4\;$ ?\ $\endgroup$ – DonAntonio Mar 7 '18 at 9:51
  • $\begingroup$ 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 $\endgroup$ – JakeRyan34 Mar 7 '18 at 9:53
  • $\begingroup$ Yes, do that.... $\endgroup$ – DonAntonio Mar 7 '18 at 9:54

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

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

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

Using Prove that $a^{(p-1)/2} \equiv 1$ (mod p) and $a^{(p-1)/2} \equiv -1$ (mod p),

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

  • $\begingroup$ 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 $\endgroup$ – JakeRyan34 Mar 7 '18 at 10:09
  • $\begingroup$ @JakeRyan34, Have you understood uptil then? $\endgroup$ – lab bhattacharjee Mar 7 '18 at 10:12
  • $\begingroup$ I think so. I'm working my way through that other thread and comparing it to this problem. $\endgroup$ – JakeRyan34 Mar 7 '18 at 10:17
  • $\begingroup$ @JakeRyan34, The exponent is $$1+\dfrac{(p-1)}2$$ $\endgroup$ – lab bhattacharjee Mar 7 '18 at 10:17
  • $\begingroup$ In that case I don't understand haha. Whose answer should I be looking at on that thread? $\endgroup$ – JakeRyan34 Mar 7 '18 at 10:20

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.