Primitive Root of odd prime p

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

Quote:

---

Originally Posted by kingwinner

http://sites.google.com/site/asdfasdf23135/nt6.JPG



[also under discussion in math links forum]

---

http://www.mathhelpforum.com/math-he...ive-roots.html

Tonio

Quote:

---

Originally Posted by chiph588@

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

---

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