Finding the last 4 digits of a huge power

Question

I know this is more of a 'aops' type of question but here we go, I went to this math competition last year and there was this one problem that clearly I didn't solve but it recently came back to my mind and I want to know how to go about such problem:

Find the last 4 digits of the number: $$2^{{10}^{2018}}$$

My intuition is that one should probably use modular arithmetic on this one, the first things that came to my mind when I saw this one where: Chinese remainder Theorem and Binomial sums, I wasn't able to do much unfortunately... I've read through the "How do I compute $a^b$ (mod c) by hand?" question but most of the answers rely on a and c being coprime which in my case $(2,10^4)=2$ is not true, the answers cover a few cases when a and c are not coprime but nothing very similar to my case...

Answer 1

You have $10000 = 2^45^4 = 16\cdot 625.$ You need to find $2^{10^{2018}} \pmod{10000}$ and the Chinese Remainder Theorem will do this nicely. First

$$2^{10^{2018}} \equiv 0 \pmod{16}.$$

Second, note that $\phi(625)=500$, so since $500$ divides $10^{2018},$

$$2^{10^{2018}} \equiv 1 \pmod{625}.$$

Then CRT gives $9376$ for the final answer.

Answer 2

The first thing we can do is to break down $10^4$ to $2^4\cdot5^4$ and use CRT afterwards.

Clearly, $2^{{10}^{2018}}\equiv0\pmod{2^4}$. To calculate $2^{{10}^{2018}}\pmod{5^4}$, we can use Euler's Theorem: $$\phi(5^4)=4\cdot5^3\mid10^{2018} \rightarrow2^{{10}^{2018}}\equiv1\pmod{5^4}$$Therefore, $$2^{{10}^{2018}}\equiv2^0\equiv1\pmod{5^4}$$And finally, use CRT to get the final answer. $$\begin{cases}2^{{10}^{2018}}\equiv0\pmod{2^4}\\2^{{10}^{2018}}\equiv1\pmod{5^4}\end{cases}\implies2^{{10}^{2018}}\equiv\boxed{9376}\pmod{10^4}$$