# $m>2$ and $n > 2$ are relatively prime $\Rightarrow$ no primitive root of $mn$

Show that if $m>2$ and $n > 2$ are relatively prime, there is no primitive root of $mn$

I know that $mn > 4$, and thus $\varphi(mn)$ is an even number so that I might write $\varphi(mn) = 2x$ for an integer $x$. If I could prove that $x = \frac{1}{2} \varphi(mn)$ is the order of some integer $a$ modulo $mn$, then I've proven that there is no primitive root of $mn$.

Since $m$ and $n$ are relatively prime, I can write the equation \begin{align} a^{\frac{1}{2} \varphi(mn)} \equiv 1 \pmod{mn} \end{align} as a set of congruences \begin{align} \begin{cases} a^{\frac{1}{2} \varphi(mn)} \equiv 1 \pmod{m} \\ a^{\frac{1}{2} \varphi(mn)} \equiv 1 \pmod{n} \end{cases} \end{align} This is where I get stuck. Am I on the right track? Or is there a better way to prove this?

We know that $a^{\phi(m)}\equiv1$ mod $m$ if $(a,m)=1$ and $a^{\phi(n)}\equiv1$ mod $n$ if $(a,n)=1$. Now let $L=\text{lcm}(\phi(m),\phi(n))$. Then $a^L\equiv1$ mod both $m$ and $n$ if $(a,mn)=1$. So if $(m,n)=1$, then $a^L\equiv1$ mod $mn$ for all $(a,mn)=1$. Finally, if $m,n\gt2$, then $2$ divides both $\phi(m)$ and $\phi(n)$, hence $L\le\phi(m)\phi(n)/2=\phi(mn)/2$ (the final equality because $m$ and $n$ are relatively prime). So there is no element of order $\phi(mn)$, which is to say there is no primitive root.

Remark: This is essentially the same proof as in lhf's answer (which I didn't see until I finished posting).

Carmichael's reduced totient $\lambda(m)$ and $\lambda(n)$ are both even, so $\lambda(mn) < \phi(mn)$ and there is no primitive root.

You're on the precise track.

We have $U(mn) \cong U(m) \times U(n)$.

Now both $U(m)$ and $U(n)$ have even order.

Therefore, $gcd(\phi(m),\phi(n)) \ge 2$, which implies $lcm(\phi(m),\phi(n)) < \phi(m)\phi(n)=\phi(mn)$.

Thus, $U(mn)$ cannot have an element of order $\phi(mn)$.

• – Bill Dubuque Nov 8 '16 at 14:54

$A=\Bbb Z/mn\Bbb Z$ has always divisors of zero in particular $mn=0$. If $a$ were a primitive root then for all element $x$ distinct of $0$ in $A$ we have $x=a^k$ for some integer $k$. It follows $m=a^s$ and $n=a^t$ for some integers $s$ and $t$. But then $mn=a^{s+t}=0$ absurde.

• I'm not familiar with the notation $A= \mathbb{Z} / mn \mathbb{Z}$. – SBS Nov 8 '16 at 14:29
• @SBS That are the congruence classes modulo $mn$, so basically the integers form $0$ to $mn-1$. (The second is not completely accurate, but perhaps easier to understand). – wythagoras Nov 8 '16 at 14:40