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
 A: ${\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}$
A: $2^5=32$ and $32^2=1024$, i.e. $2^{10}=1024$. Then $770+3\cdot77=770+231=1001$, so $2^{10}=1024-1001=23\mod 77$. Then $23^2=529$ and $77\cdot 7=11\cdot 49=539$, hence $2^{20}=23^2=529-539=-10\mod 77$. Then, $2^{30}=23\cdot(-10)=-230=-230+231=1\mod 77$. Thus $2^{37}=2^7\mod 77$ hence $2^{37}=128-77=51\mod 77$. This is also the answer that my computer gives me. 
You could also take a look at wiki, Modular_exponentiation
A: The answers above are good, I am just posting a different way here.
Directly consider modulo 77. $2 \equiv 2, 2^2 \equiv 4, 2^4 \equiv 16, 2^8 \equiv 25, 2^{16} \equiv 9, 2^{32} \equiv 4$ (just do squaring modulo 77 for some time). Since $2^{37} = 2^{32+4+1}$, so we can have $2^{37} \equiv 4 \times 16 \times 2 \equiv 51 \mod 77$.
This method is relatively bad in this scenario, but it works well (can I say "the best"?) in general.
A: Carmichael function $\lambda(77)=30$
As $(2,77)=1,2^{30}\equiv1\pmod{77}\implies2^{37}=2^7\cdot2^{30}\equiv2^7\cdot1\pmod{77}$
Finally, $2^7\equiv51\pmod{77}$
A: Hint: $2^3=8=7+1$ and $2^5=32=33-1=3\cdot11-1$. Using this, evaluate the remainders of $2^{37}$ when divided by $7$ and $11$, respectively. This will yield a Diophantine equation of the form $0\le7k+a=11n+b<77$, which is trivial to solve.
