# Show that if $m$ in $\mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$.

Show that if $$m$$ in $$\mathbb{Z}$$ has greatest common divisor $$1$$ with $$21$$, then $$m^{6}-1$$ is divisible by $$63$$. Also, I have to work in $$\mathbb{Z}/63 \mathbb{Z}^{*}$$, thus the group $$63$$ modulo $$\mathbb{Z}$$ under multiplication.

So in other words, I have to prove $$m^{6} \equiv 1 (\mod 63)$$.

I have no idea how to tie the fact that $$m$$ has $$1$$ as gcd with $$21$$ together with working in the $$63$$ modulo $$\mathbb{63}$$ group. I would really appreciate some hints or suggestions guide me in the right direction.

$$(m,7)=1\Rightarrow m^{\phi(7)}=m^{6}\equiv 1 \pmod{7}$$

and

$$\begin{cases} m\equiv 1\pmod{3}\Rightarrow 9|(m-1)(m^2+m+1)(m^3+1)=m^6-1\\ m\equiv 2 \pmod{3} \Rightarrow 9|(m^3+1)|(m^6-1) \end{cases}\Rightarrow m^6\equiv1\pmod{9}$$

Hint: The fact that $$(m,21)=1$$ implies, clearly, that $$(m,63)=1$$. Hence we can use Euler's Theorem, which says that $$x^{\phi(n)}=1$$ mod $$n$$ for all $$n$$, and $$x$$ coprime to $$n$$. Here, $$\phi$$ is Euler's totient function. Can you proceed further?

• Using Eulers totient function, I would say $\varphi(63)=\varphi(3^{2} \cdot 7) = \varphi( ( 3^{2}-3^{1}) \cdot 7) = \varphi(42)$. Substracting $42$ from $63$ gives $21$, thus I could work in $m^{6} \equiv 1 (\mod 21)$, correct? But I don't see how this makes the problem easier. Mar 23 '19 at 13:42
• @Mathbeginner there's no need to work mod $21$, Euler's theorem gives you mod $63$, which is exactly what you want. (i.e. use $n=63$ and $x=m$ immediately) Mar 23 '19 at 15:18
• But that would be just stating that since we know $m \equiv 1 (\mod 21)$, this implies $m \equiv 1 (\mod 63)$ and that would be the end of it. Is that what you are saying? Mar 24 '19 at 8:31

The key point is that $$21$$ and $$63$$ have the same prime divisors.

Indeed, since $$21 = 3 \cdot 7$$ and $$63 = 3^2 \cdot 7$$, we have $$\gcd(m,21)=1 \iff \gcd(m,3)=1=\gcd(m,7) \iff \gcd(m,63)=1$$ Then Euler's theorem gives $$m^6\equiv 1 \bmod 7, \quad m^6\equiv 1 \bmod 9$$ Therefore, $$m^6\equiv 1 \bmod 63$$.

Carmichael Function $$\lambda(63)=[\lambda(9),\lambda(7)]=6$$

$$(m,21)=1\implies (m,7)=(m,3)=1$$

• Downvoting this seems a bit harsh. Though it may well be beyond the OP's knowledge level, it may help to introduce readers to this handy generalization. Mar 23 '19 at 15:30
• @BillDubuque, Down-voting like up-voting is not controlled here in MSE. Just now received one: math.stackexchange.com/questions/771320/… .Sometimes I try to learn the flaw: math.stackexchange.com/questions/3157905/… Mar 24 '19 at 6:10