If primitive root modulo $mn$, then primitive root modulo $m$ and $n$

Question

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?

Answer 1

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.

Answer 2

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