Primitive Root of odd prime p

Printable View

Mar 1st 2010, 04:16 PM
kingwinner

Primitive Root of odd prime p

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

[also under discussion in math links forum]
Mar 1st 2010, 09:53 PM
chiph588@

Let $p\equiv 1 \mod{4} \text{ and } k\mid p-1$ be even.
Then $(-g)^k = g^k \not\equiv 1 \mod{p}$ since $g$ is a primitive root.

If $k\mid p-1$ is odd, then $(-g)^k = -g^k$ , but $g^k \not\equiv -1 \mod{p}$ for this would mean $g^{2k} \equiv 1 \mod{p}$ which we know to be false since $2k < p-1$ .

Therefore $-g$ is a primitive root if $p\equiv 1 \mod{4}$ .

If $p\equiv 3 \mod{4}$ then $p=4k+3$ , so $\frac{p-1}{2}=2k+1$ i.e. $\frac{p-1}{2}$ is odd. Therefore $(-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}}$ .

Now since $2\mid p-1, \; g^{p-1} = \left(g^{\frac{p-1}{2}}\right)^2$ . Let $x=g^{\frac{p-1}{2}}$ .

We know $x^2 \equiv 1 \mod{p} \implies p\mid (x+1)(x-1) \implies x\equiv 1 \text{ or } -1 \mod{p}$ . But since $g$ is a primitive root, $x \not\equiv 1 \mod{p} \implies x\equiv -1 \mod{p}$ .

Therefore $(-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}} \equiv (-1)(-1) = 1 \mod{p}$ . Hence $-g$ is not a primitive root for $p\equiv 3 \mod{4}$ .
Mar 2nd 2010, 02:09 AM
tonio

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
Mar 2nd 2010, 09:33 AM
kingwinner

Quote:

Originally Posted by chiph588@

Let $p\equiv 1 \mod{4} \text{ and } k\mid p-1$ be even.
Then $(-g)^k = g^k \not\equiv 1 \mod{p}$ since $g$ is a primitive root.

If $k\mid p-1$ is odd, then $(-g)^k = -g^k$ , but $g^k \not\equiv -1 \mod{p}$ for this would mean $g^{2k} \equiv 1 \mod{p}$ which we know to be false since $2k < p-1$ .

Therefore $-g$ is a primitive root if $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!
Mar 2nd 2010, 11:10 AM
chiph588@

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 $\frac{p-1}{2}$ is the largest divisor strictly less than p-1.

But we know $\frac{p-1}{2} = 2n$ and $k\mid p-1$ is odd.

So, since $k \neq \frac{p-1}{2}$ and $\frac{p-1}{2}$ is the largest proper divisor we have $k<\frac{p-1}{2}$

i.e. $2k < p-1$ .