Monday, April 25, 2016

elementary number theory - How to find last two digits of $2^{2016}$



What should the 'efficient' way of finding the last two digits of $2^{2016}$ 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...