# Thread: Primitive Root of odd prime p

1. ## Primitive Root of odd prime p

[also under discussion in math links forum]

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

3. Originally Posted by kingwinner

[also under discussion in math links forum]

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

Tonio

4. 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!

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