2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Mar 23 '19 at 13:42
  • $\begingroup$ @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) $\endgroup$
    – YiFan
    Mar 23 '19 at 15:18
  • $\begingroup$ 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? $\endgroup$ Mar 24 '19 at 8:31
1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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

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

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.