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?
Best Answer
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).