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