1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not familiar with the notation $A= \mathbb{Z} / mn \mathbb{Z}$. $\endgroup$ – SBS Nov 8 '16 at 14:29
  • $\begingroup$ @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). $\endgroup$ – wythagoras Nov 8 '16 at 14:40

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.