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?

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

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$

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.