Primitive roots generated from a primitive root

Question

Let $p$ be a prime number, and let $a$ be a primitive root $\mod p$.

Is it true that $a^m$ is a primitive root if and only if $\gcd(m,p-1)=1$?

One direction is correct: if $a^m$ is a primitive root, then let $d = gcd(m,p-1)$. Then $dq_1 = m, dq_2 = p-1$, where $q_1,q_2\in\mathbb{Z}$, and $q_2\leq p-1$. We then have that $$ \left(a^m\right)^{q_2} = \left(a^{dq_1}\right)^{q_2} = \left(a^{q_1}\right)^{dq_2} = \left(a^{q_1}\right)^{p-1} $$ From Fermat's little theorem, the rightmost element is congruent to $1\mod{p}$, since $a < p$. From this, we conclude that since $a^m$ is a primitive root, and $q_2\leq 18$, then necessarily $q_2 = 18$, which means $d=1$.

I am not sure about the other direction: does $gcd(m,p-1)=1$ imply $a^m$ is primitive, given $a$ is primitive?

Answer 1

Given that $p>2$ is prime and that $a$ is a primitive root modulo $p$, we know that $a^j\equiv 1 \bmod p$ if and only if $j$ is a multiple of $p{-}1$, that is, when $j\equiv 0 \bmod p{-}1$. Thus:

$\Rightarrow$:
Given $b=a^m$ with $\gcd(m,p-1)=1$, we know that $mk \equiv 0 \bmod p{-}1$ if and only if $k\equiv 0 \bmod p{-}1$. Thus $b^k\equiv 0 \bmod p$ if and only if $k\equiv 0 \bmod p{-}1$ and $b$ is a primitive root $\bmod p$

$\Leftarrow$:
Given $c=a^n$ with $d:=\gcd (n,p-1)>1$, we can find $\ell= (p{-}1)/d<p{-}1$ and then $n\ell \equiv 0 \bmod p{-}1$ giving $c^\ell\equiv 1 \bmod p$ and thus $c$ is not a primitive root $\bmod p$.

Answer 2

Given that $a$ is a primitive root $\pmod p$, there is one basic way to generate a primitive root $\pmod p$ depending on the congruence of $p \pmod 4$. If $p = 1 \pmod 4$, then $-a$ is a primitive root. If $p = 3 \pmod 4$, then $-a^2$ is a primitive root.

Regardless of the prime $p$ and the primitive root $a$, If $a$ is a primitive root $\pmod p$, $a^n$ is also a primitive root $\pmod p$ if and only if $\gcd(n,p-1)=1$. To prove this, let $a$ be a primitive root $\pmod p$. The order of $a \pmod p$ is $p-1$ and $a^{p-1}=1 \pmod p$ but not $a^{(p-1)/q}$ for every prime $q$ dividing $p-1$. So if $gcd(n,p-1)=q$ and therefore not $1$, $a^{(p-1)/q}=1 \pmod p$ and the order of $a^n \pmod p$ is $(p-1)/q$, not $p-1$. Use this to prove the first two trivial statements.