Thread: 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.

The order of the multiplicative group $\displaystyle \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 $\displaystyle \mathbb{Z}_{p}^\times$ must divide p-1.

Do you get where this is going?

not really?

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 $\displaystyle \gcd(r,p)=1$. It should be a known result that if $\displaystyle d$ is order of $\displaystyle r$ then $\displaystyle r^d \equiv 1(\bmod p)$ and $\displaystyle d$ divides $\displaystyle p-1$. Therefore, if for all $\displaystyle d>1$ which divide $\displaystyle p-1$ we have $\displaystyle r^d \not \equiv 1(\bmod p)$ then $\displaystyle r$ must be a primitive root. That is essentially what you problem is saying.