If $m|n$ and $a$ is a primitive root of $n$, show that $a$ is a primitive root of $m$ (understanding a tip)

Question

I saw the answer to this question and it is the same problem, but i didn't get how to use the tip S.C.B gave.

This was the tip:

$"$First, assume that it is not $a$ primitive root $(\text{mod m})$. Then we have that there exists such $r<\phi(m)$ such that $$a^r\equiv 1(\text{mod m})$$
Now use that, if $n=mk$
$$ϕ(mk)=ϕ(m)ϕ(k)\frac{d}{ϕ(d)}≥ϕ(m)ϕ(k)>rϕ(k)$$
where $d=gcd(m,k)"$

and i saw the answer to this question using group theory, but i want an answer using elementary number theory, if you have a different answer, or tip, it would be good as well.

What i tried was this:

$n=mk$, then
$$a^{\phi(n)}\equiv 1(\text{mod n})\Rightarrow a^{\phi(mk)}\equiv1(\text{mod mk}) \Rightarrow a^{\phi(mk)}\equiv1(\text{mod m})$$

But i don't know how to follow from here

Answer 1

Here's another approach.

Let $\phi_n$ denote the set of elements which are coprime to $n$.

First, show that $a$ is a primitive root modulo $n$ iff $ \{ a^r \pmod{n} \} = \phi_n $.

Second, show that for $m \mid n$, $ \{ k \pmod{m} | k \in \phi(n) \} = \phi_m$

(Proof of the hard part) Suppose we have $ \gcd(a, m) = 1$, and we want to "lift" it to an element in $\phi(n)$.
Use CRT to solve the following system of congruences:
- $ A \equiv a \pmod{p^i}$, for every prime $p$ that divides $m$ and $n$, and $ p^i \mid\mid n$
- $ A \equiv 1 \pmod {q^i}$, for every prime $q$ that doesn't divide $m$ but divides $n$, and $q^i \mid \mid n$
CRT guarantees us a solution since the congruences are coprime, and we have $ A \equiv a \pmod{m} $ as well as $ \gcd(A, n) = 1$.

Hence, conclude that $ a$ is a primitive root mod $m$ in the problem.