Let p be an odd prime. Prove that r is a primitive root modulo p if, and only if, r $\displaystyle \in Z^+$ such that gcd (r,p) = 1 and
$\displaystyle r^{(p-1)/q}$ is not congruent to 1 mod p
Let p be an odd prime. Prove that r is a primitive root modulo p if, and only if, r $\displaystyle \in Z^+$ such that gcd (r,p) = 1 and
$\displaystyle r^{(p-1)/q}$ is not congruent to 1 mod p
for all prime divisors q of p-1
Direction ==> is immediate from definition, and direction <== follows from assuming that ord(r) = m < p-1