1. ## Primitive Root Problem

Let p be an odd prime. Prove that r is a primitive root modulo p if, and only if, r $\in Z^+$ such that gcd (r,p) = 1 and
$r^{(p-1)/q}$ is not congruent to 1 mod p

for all prime divisors q of p-1

2. Originally Posted by Janu42
Let p be an odd prime. Prove that r is a primitive root modulo p if, and only if, r $\in Z^+$ such that gcd (r,p) = 1 and
$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

and then dividing p-1 by m.

Tonio