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

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.

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

• $ϕ(mk)=ϕ(m)ϕ(k)$ only if $m,k$ are coprime, no? Commented Nov 6, 2020 at 7:06
• Yes, but $\phi(mk)=\phi(m)\phi(k)\frac{d}{\phi(d)}$ where $d=gcd(m,k)$ Commented Nov 6, 2020 at 13:41

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.

• I proved the first part, but i'm having trouble to prove the second one, i know that $gcd(k,n)=1\Rightarrow gcd(k,m)=1$ and we have also $k\equiv j (\text{mod n}) \Rightarrow k\equiv j(\text{mod m})$ this show that $\{k(\text{mod m})|k\in\phi(n)\} \subseteq \phi(m)$ but i'm having trouble to prove the $\supseteq$ (i think it's because $\phi(m)\subseteq\phi(n)$ but i'm not sure how to explain. And how to transition to prove this for the powers of $a$, because how do i know that there are no cases like $a^j\equiv l(\text{mod n})$ and $a^i\equiv l+m(\text{mod n})$ with $i,j<\phi(m)$? Commented Nov 6, 2020 at 13:53
• @user8785084 You're overthinking it. Just apply CRT. I've included that part as a spoiler if you need more help. (Note that I'm not solving via $a^j \equiv l$, because of the equivalence set up in the first part.) Commented Nov 6, 2020 at 16:46
• Note that $\phi(m) \not \subset \phi(n)$. For example, with $m = 3, n = 6$, we have $\phi(3) = \{ 1, 2 \}$ and $\phi(6) = \{ 1, 5 \}$. As such, we do need to "lift" an element from $\phi(m)$ up into an element of $\phi(n)$. Commented Nov 6, 2020 at 16:52