1
$\begingroup$

In the solutions it used Chinese remainder theorem in the following way: $6^{65}\equiv 1 \pmod 5 $ and $ 6^{65} \equiv 0 \pmod{16} $. I can see how they got the first congruence but am really struggling to see it for the second one. Any help would be much appreciated!

$\endgroup$
  • 2
    $\begingroup$ $6^{65}=2^{65}3^{65}$, which is a multiple of $2^4=16$. $\endgroup$ – vadim123 Apr 14 '18 at 16:00
2
$\begingroup$

$6^{65}=2^{4}2^{61}3^{65}$ is clearly a multiple of $16$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If $m=pq$ you have an arrow $\mathbb{Z}/m\mathbb{Z}$ (remainders by $m$) to $\mathbb{Z}/q\mathbb{Z}$ (remainders by $q$) which is simply processed by "redividing" the remainder mod m by $q$ call this arrow $\phi_{q,m}$. Now, by Chinese remainder theorem and Bezout, you see that, if $m=pq$ and if $p,q$ are coprime, the arrow $$ \phi_{p,q;m}: \mathbb{Z}/m\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z} $$ such that $$ \phi_{p,q;m}(h)=(\phi_{p,m}(h),\phi_{q,m}(h)) $$
is one-to-one. Then, with $m=80, p=5,q=16$ you get that there is only ONE number $h\in \mathbb{Z}/80\mathbb{Z}$ such that $\phi_{5,16;80}(h)=(1,0)$, it is of the form $16k$ hence $k=1$, you get $6^{65}\equiv 16 \mod 80$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$$6^4\equiv16\pmod{80}\\16\times6=96=80+16\Rightarrow 6^{4+n}\equiv16\pmod{80}, \text{ for all }\space n\ge1$$ Consequently $$6^{65}\equiv16\pmod{80}$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Note: $$\begin{align} 6 &\equiv 1\pmod 5 \\ 6^{61} &\equiv 1 \pmod 5 \\ 6^{61}\cdot 2^4 &\equiv 1\cdot 2^4 \pmod {5\cdot 2^4}\\ 3^4 &\equiv 1\pmod{80}\\ 6^{61}\cdot 2^4\cdot 3^4 &\equiv 1\cdot 2^4\cdot 1 \pmod{80}\\ 6^{65} &\equiv 16 \pmod{80}.\end{align}$$

| cite | improve this answer | |
$\endgroup$

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.