Sunday, 21 August 2016

number theory - Finding the last 4 digits of a huge power




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: 2102018




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 ab (mod c) by hand?" question but most of the answers rely on a and c being coprime which in my case (2,104)=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



You have 10000=2454=16625. 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.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...