What is the remainder when $ 6^{65} $ is divided by 80? 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!
 A: $6^{65}=2^{4}2^{61}3^{65}$ is clearly a multiple of $16$.
A: 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$.
A: $$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}$$
A: 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}$$
