5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Instead of considering powers of $2$ mod $10$, consider them mod $100$. It's not entirely elegant but it shouldn't be too much of a calculation. $\endgroup$ May 29 '16 at 15:18
7
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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}$

$\endgroup$
3
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.