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 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 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 . It should be a known result that if is order of then and divides . Therefore, if for all which divide we have then must be a primitive root. That is essentially what you problem is saying.