Let $a$ be a primitive root modulo $mn$. Show that $a$ is also primitive root modulo $m$ and $n$.
Showing $(a,mn)=1\Longrightarrow (a,m)=(a,n)=1$ is not a problem. The problem is showing $a^{\varphi (m)} \equiv 1\pmod{m}$ where $\varphi (m)$ is the least natural number for which the congruence holds.
Initial thought:
Let $A :=\{x|a^x\equiv 1\pmod{m}\}\subset\mathbb{N}$, obviously $A\neq\emptyset$ so it contains the smallest element $r$. Must show that $r=\varphi (m)$. Supposing for a contradiction that $r<\varphi (m)$ I would need it somehow to contradict the fact that $$a^{\varphi (mn)}\equiv 1\pmod{mn} $$ where $\varphi (mn)$ is the least for which said congruence holds.

How should one go about finding a contradiction?


2 Answers 2


First, assume that it is not a primitive root $\pmod m$. Then we have that there exists such $r < \phi (m)$ $$a^r \equiv 1 \pmod m$$

Now use that $$\phi (mn) = \phi (m)\phi (n) \frac{ d}{\phi (d)} \ge \phi(m) \phi (n)> r \phi (n)$$

From here.

  • $\begingroup$ Can you elaborate on this? How do you get a contradiction? $\endgroup$
    – Calvin Lin
    Nov 6, 2020 at 16:51
  • $\begingroup$ @CalvinLin $a^{\phi(n)} \equiv 1 \pmod n$ while $a^r \equiv 1 \pmod m$. Thus $a^{r\phi(n)} \equiv 1 \pmod m$, $a^{r\phi(n)} \equiv 1 \pmod n$. But I think I made a mistake here, as the above two congruences do not necessarily imply $a^{r\phi(n)} \equiv 1 \pmod {mn}$. I'll look at it later. $\endgroup$
    – S.C.B.
    Nov 8, 2020 at 1:02

Because a primitive root modulo $mn$ exists, it is necessary and sufficient that $mn\in\{2,4,p^k,2p^k\}, p>2, k\in\mathbb{N}$. The interesting cases are $mn\in\{p^k,2p^k\}$.

  1. Let $mn=p^k$ and $x$ a primitive root modulo $p^k$. It follows that $x$ is a primitive root modulo $p$. Then, modulo $p^2$, at least one of $x$, $x+p$ is a primitive root. It turns out $x$ is a primitive root modulo $p^2$, for otherwise $x$ is not a primitive root modulo $p$ and therefore not a primitive root modulo $p^k$.
    Provided $x$ is a primitive root modulo $p^2$, it's also a primitive root modulo $p^r,r>2$.

  2. Let $mn=2p^k$. The only interesting case is $(m,n)>1$ that is $m=2p^s$ and $n=p^t$ such that $s+t=k$. The assertation holds for $n$ and consequently for $m$, otherwise we would have $r<\varphi (2p^s) =\varphi (p^s)$: $$x^r\equiv 1\pmod{2p^s}\Longrightarrow x^r\equiv 1\pmod{p^r} $$ which then, in turn, implies $x$ is not a primitive root modulo $p^k$ and consequently not a primitive root modulo $2p^k=mn$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .