# Primitive roots generated from a primitive root

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?

• try to use the fact set of invertible elements of Z/pZ form a cyclic group. – SAUVIK Apr 1 '16 at 11:33
• More generally, $ord(a^m) = (p-1)/ gcd(m,p−1)$. – lhf Apr 1 '16 at 11:41
• I was hoping to prove this using elementary number theoretic tools without group theory. How can I show this formula? – JonTrav Apr 1 '16 at 11:53
• – lab bhattacharjee Apr 1 '16 at 12:12
• More generally, we know, $$ord_ma=d, ord_m(a^k)=\frac{d}{(d,k)}$$ Proof @Page#95) of archive.org/details/NumberTheory_862 – lab bhattacharjee Apr 1 '16 at 12:14

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$.
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.