What is the remainder when $ 6^{65} $ is divided by 80?

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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