# Finding the last 4 digits of a huge power [duplicate]

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

## marked as duplicate by Parcly Taxel, Chinnapparaj R, José Carlos Santos, ArsenBerk, VladhagenOct 29 '18 at 16:38

• It's about computing $2^a$ modulo $10^4$. The sequence $2^a$ will be eventually periodic modulo $10^4$, so really it's a question of determining the period, and seeing how your particular $a=10^{2018}$ relates to that period. – Lord Shark the Unknown Oct 28 '18 at 6:59
• The statement of the problem makes me suspect that this is from some form of recent competition. Where is this problem from, exactly? – Arthur Oct 28 '18 at 7:09
• @Arthur It's the second phase of an Italian competition, I will roughly translate it as "Group Mathematical contest of Tor Vergata" (which is a university in Rome) if you're interessed here's the link to the website you can find the texts and everything but they're in italian: mat.uniroma2.it/olimpiadi.php – Spasoje Durovic Oct 28 '18 at 7:18
• It seems to have been held in March, which is fine. We don't want people to get help with ongoing competitions, but that's not the case here as far as I can see. – Arthur Oct 28 '18 at 7:26
• @Arthur Oh okay yeah, the competition was held in March and the solutions are online, but they only give you the result not how it was obtained, that's why I asked: problemisvolti.it/Docu/GaSquadre/GaSquadreTVG18.pdf – Spasoje Durovic Oct 28 '18 at 8:30

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.

• Thanks, it was $10000$ instead of $1000$, I got a response for this one on another forum just a few minutes before yours... – Spasoje Durovic Oct 28 '18 at 13:43
• OK, I'll fix it up. – B. Goddard Oct 29 '18 at 0:54

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