1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Who gave that hint? How come you're not sure what "property 6" is?? $\endgroup$
    – DonAntonio
    Commented Mar 7, 2018 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
    Commented Mar 7, 2018 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
    Commented Mar 7, 2018 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
    Commented Mar 7, 2018 at 9:53
  • $\begingroup$ Yes, do that.... $\endgroup$
    – DonAntonio
    Commented Mar 7, 2018 at 9:54

2 Answers 2

2
$\begingroup$

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$

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

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

$\endgroup$
8
  • $\begingroup$ $p \equiv 1 mod(4)$ implies that $\frac{p-1}2$ is even right? $\endgroup$
    – JakeRyan34
    Commented Mar 7, 2018 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$ Commented Mar 7, 2018 at 14:20
  • $\begingroup$ Wouldn't that mean that $(-1)^\frac{p-1}2 = 1$ since $\frac{p-1}2$ is even? $\endgroup$
    – JakeRyan34
    Commented Mar 7, 2018 at 15:09
  • 1
    $\begingroup$ Do you agree that $(-1)^2 3^2=(-3)^2$? That's the same idea. $\endgroup$ Commented Mar 7, 2018 at 15:39
  • 1
    $\begingroup$ ohhh i see what you mean, thanks $\endgroup$
    – JakeRyan34
    Commented Mar 7, 2018 at 15:51

You must log in to answer this question.

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