Q:

Prove that $r$ is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$

Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root
  modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p − 1$.

The only if direction is trivial, I can multiply $q$ to get $(r^{(p-1)/q})^q\equiv1^q\pmod{p}$.  So, $r$ is a primitive root. How do I do the other direction? Can someone give me a hint or suggestion? Thanks

A:

Hints. The primitive roots mod $p$ are exactly the generators of $(\mathbb{Z}/p\mathbb{Z})^\times\cong\mathbb{Z}/(p-1)\mathbb{Z}$. Hence, $r$ is a primitive root mod $p$ if and only if the order of $r$ is $p-1$. Besides, since $r\in(\mathbb{Z}/p\mathbb{Z})^\times$, using Lagrange's theorem the order of $r$ is a divisor of $p-1$.

