http://sites.google.com/site/asdfasdf23135/nt6.JPG
[also under discussion in math links forum]
Printable View
http://sites.google.com/site/asdfasdf23135/nt6.JPG
[also under discussion in math links forum]
Let $\displaystyle p\equiv 1 \mod{4} \text{ and } k\mid p-1 $ be even.
Then $\displaystyle (-g)^k = g^k \not\equiv 1 \mod{p} $ since $\displaystyle g $ is a primitive root.
If $\displaystyle k\mid p-1 $ is odd, then $\displaystyle (-g)^k = -g^k $, but $\displaystyle g^k \not\equiv -1 \mod{p} $ for this would mean $\displaystyle g^{2k} \equiv 1 \mod{p} $ which we know to be false since $\displaystyle 2k < p-1 $.
Therefore $\displaystyle -g $ is a primitive root if $\displaystyle p\equiv 1 \mod{4} $.
If $\displaystyle p\equiv 3 \mod{4} $ then $\displaystyle p=4k+3 $, so $\displaystyle \frac{p-1}{2}=2k+1 $ i.e. $\displaystyle \frac{p-1}{2} $ is odd. Therefore $\displaystyle (-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}} $.
Now since $\displaystyle 2\mid p-1, \; g^{p-1} = \left(g^{\frac{p-1}{2}}\right)^2 $. Let $\displaystyle x=g^{\frac{p-1}{2}} $.
We know $\displaystyle x^2 \equiv 1 \mod{p} \implies p\mid (x+1)(x-1) \implies x\equiv 1 \text{ or } -1 \mod{p} $. But since $\displaystyle g $ is a primitive root, $\displaystyle x \not\equiv 1 \mod{p} \implies x\equiv -1 \mod{p}$.
Therefore $\displaystyle (-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}} \equiv (-1)(-1) = 1 \mod{p} $. Hence $\displaystyle -g $ is not a primitive root for $\displaystyle p\equiv 3 \mod{4} $.
Hi, thanks for your help! I have some questions about your proof.
1) When you say k|p-1 is odd or k|p-1 is even, do you include the case k=p-1? Or are you only referring to the divisors of p-1 that are strictly less than p-1?
2) Also, how do you know that 2k is strictly less than p-1? (i.e. 2k < p-1?)
Thank you very much!
1.) Yes, I meant to say k is strictly less than p-1
2.) What's the smallest divisor of p-1 not equal to 1? The answer is 2.
Therefore $\displaystyle \frac{p-1}{2} $ is the largest divisor strictly less than p-1.
But we know $\displaystyle \frac{p-1}{2} = 2n $ and $\displaystyle k\mid p-1 $ is odd.
So, since $\displaystyle k \neq \frac{p-1}{2} $ and $\displaystyle \frac{p-1}{2} $ is the largest proper divisor we have $\displaystyle k<\frac{p-1}{2} $
i.e. $\displaystyle 2k < p-1 $.