Theorem
If \(a\) is a primitive root modulo \(m\) then, \(a^r\) is a primitive root modulo \(m\) if and only if \(\gcd(r,\phi(m)) = 1\)
Proof
Let \(a\) be a primitive root modulo \(m\). By definition, we know that \(a\) has order \(\phi(m)\). We also know that the order of \(a^r\) (By This) is
$$
\begin{align*}
|a^r| = \frac{\phi(m)}{\gcd(\phi(m), r)}
\end{align*}
$$
But this means that \(|a^r| = \phi(m)\) if and only if \(\gcd(\phi(m), r) = 1\).
References
- Number Theory by George E. Andrews