# Thread: Primitive Roots

1. ## Primitive Roots

Let p be an odd prime number and let r be an integer with p not dividing r. Prove that r is a primitive root modulo p if and only if r^((p-1)/q) is not congruent to 1 mod p for all prime divisors q of p-1.

2. The order of the multiplicative group $\mathbb{Z}_{p}^\times$ is p-1.
The idea is that r is a primitive root if the order of r is p-1.
The order of any element of $\mathbb{Z}_{p}^\times$ must divide p-1.

Do you get where this is going?

3. not really?

4. Originally Posted by mndi1105
Let p be an odd prime number and let r be an integer with p not dividing r. Prove that r is a primitive root modulo p if and only if r^((p-1)/q) is not congruent to 1 mod p for all prime divisors q of p-1.
Let $\gcd(r,p)=1$. It should be a known result that if $d$ is order of $r$ then $r^d \equiv 1(\bmod p)$ and $d$ divides $p-1$. Therefore, if for all $d>1$ which divide $p-1$ we have $r^d \not \equiv 1(\bmod p)$ then $r$ must be a primitive root. That is essentially what you problem is saying.