# 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!

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

$6^{65}=2^{4}2^{61}3^{65}$ is clearly a multiple of $16$.
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$.
$$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}$$
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}