Let $\displaystyle \Phi_n(x)$ be the $\displaystyle n$th cyclotomic polynomial. Show that $\displaystyle r$ is a primitive root $\displaystyle \mod p$ if and only if $\displaystyle \Phi_{p-1}(r) \equiv 0 \mod p$.

I suspect NonCommAlg will be the first to bite!