2
$\begingroup$

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

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$? $\endgroup$
    – user8785084
    Commented Nov 6, 2020 at 13:53
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Calvin Lin
    Commented Nov 6, 2020 at 16:46
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Calvin Lin
    Commented Nov 6, 2020 at 16:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .