Find the last two digits of $2^{2156789}$ Find the last two digits of $2^{2156789}$.
My try:
As $2156789 = 4* 539197 + 1$
The unit digit of $2^{2156789}$ is similar to the unit digit of $2^{4n+1}$ which is equal to 2.
But I'm unable to find the tens digit.  Please help me. 
 A: We obviously have $2^{2156789} \equiv 0 \pmod{2^2}$. Now as $100=2^2 \times 5^2$, we only need to find the remainder modulo $25$. Use the fact that $2^{20} \equiv 1 \pmod {25}$ from Euler's Totient Function and you will have: $2^{2156789} \equiv 2^{9} \equiv 12 \pmod {25}$
Now glue the two results using Chinese Remainder Theorem to get that the last two digits are $12$.
A: We can avoid CRT as $2^2\mid2^{2156789}$
As $(2^{2156789},100)=2^2,$
let us find $2^{2156789-2}\pmod{25}$
As $\phi(25)=20$ and $2156789-2\equiv7\pmod{20},$
$2^{2156789-2}\equiv2^7\pmod{25}\equiv3$
$\implies2^{2156789-2}\cdot2^2\equiv3\cdot2^2\pmod{25\cdot2^2}$
A: So the question is to find $a \equiv 2^{2156789} \bmod 100$.
The Carmichael function gives the maximum order of any number $\bmod 100$. Calculated as $\lambda(100) = \text{lcm}(\phi(4),\phi(25)) = \text{lcm}(2,20) =20 $. (However $2^{21}\not \equiv 2^1 \bmod 100 $ because the multiplicity of $2$ in $100 $ is $2$, but $2^{41} \equiv 2^{21} \bmod 100 $).
So we immediately know that $2^{2156789} \equiv  2^{9} \bmod 100$.  This is very easy to calculate directly, but you can run through the modular exponentiation quickly too:
$$ \begin{align}
2^4 &\equiv 16 \\
2^8 &\equiv 16^2 \equiv 56 \\
2^9 &\equiv 2\times 56 \equiv 12 \\
\hline
\end{align}$$
A: So, we want to find the last two digits of some power of two. These numbers repeat infinitely as the powers increase, therefore let us attemp to find this pattern.
Starting at 2^0 we lost all of the successive mod 100 remainders:
1, 2, 4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 4
So, 2^22 is the place where it repeats. The cycle is 20 long. However the first power can be removed.
Therefore (x-1) mod 20 = the index of the proper two digit sequence within the pattern where x is some power 2 has been raised to.
2156788 mod 20 = 8
The eighth item in the sequence is the answer...
This number is 12.
