Monday, April 25, 2016

elementary number theory - How to find last two digits of 22016



What should the 'efficient' way of finding the last two digits of 22016 be? The way I found them was by multiplying the powers of 2 because 2016=1024+512+256+128+64+32. I heard that one way would be with the Chinese Remainder Lemma but I don't really know how I should start?


Answer



Essentially we need 2^{2016}\pmod{100}



As (2^{2016},100)=4




let us find 2^{2016-2}\pmod{100/4}



Now as 2^{10}\equiv-1\pmod{25}



2^{2014}=2^{201\cdot10+4}=(2^{10})^{201}\cdot2^4\equiv(-1)^{201}\cdot2^4\equiv9\pmod{25}



\implies2^2\cdot2^{2014}\equiv2^2\cdot9\pmod{2^2\cdot25}


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...