<s>[INST] How to find $2^{37} \bmod 77$? Is there any quick way to find $2^{37} \bmod 77$?
I have tried breaking it down into 2 components for example ..
$2^{37} \bmod 7$ and $2^{37} \bmod 11$ but still no luck.
Any ideas?
Thanks
 [/INST] ${\rm mod}\ \ \ 7\!:\,\ \color{#c00}{2^3\ \equiv\ 1}\,\ \Rightarrow\ 2^{37}\equiv 2(\color{#c00}{2^3})^{12}\equiv 2(\color{#c00}1)^{12}\equiv\,\color{#b70} 2$
${\rm mod}\ 11\!:\,\ \color{#c00}{2^5\equiv -1}\,\Rightarrow\, 2^{37}\equiv 2^2(\color{#c00}{2^5})^{7}\equiv 4(\color{#c00}{-1})^{7}\equiv\color{#0a0}{ -4}\,\Rightarrow\, 2^{37} = \color{#0a0}{11n\!-\!4},\,$ so by CRT
${\rm mod}\ 7\!:\,\ \color{#b70}2\equiv 2^{37}\equiv\color{#0a0}{11n\!-\!4}\equiv -3n\!+\!3\iff 3n\equiv 1\equiv-6\iff \color{#a0f}{n\equiv -2\equiv 5}$
Therefore $\quad\ \ 2^{27}\equiv 11\color{#a0f}n\!-\!4\equiv 11(\color{#a0f}{5\!+\!7k})-4\equiv 51+77k$

Remark $\ $ Per comments, we can compute the powers using only little Fermat as follows:
${\rm mod}\ \ \ 7\!:\,\ \ \color{#c00}{2^6 \equiv 1}\ \Rightarrow\ 2^{37}\equiv 2(\color{#c00}{2^6})^{6}\equiv 2(\color{#c00}1)^{6}\equiv\,\color{#b70} 2$
${\rm mod}\ 11\!:\,\ \color{#c00}{2^{10}\equiv 1}\,\Rightarrow\, 2^{37}\equiv 2^7 (\color{#c00}{2^{10}})^{3}\equiv 128(\color{#c00}{1})^3\equiv 11^2+7\equiv\color{#0a0}{7}$
</s>