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