# Primitive Root of odd prime p

• Mar 1st 2010, 04:16 PM
kingwinner
Primitive Root of odd prime p

[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

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

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