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 22016(mod100)
As (22016,100)=4
let us find 22016−2(mod100/4)
Now as 210≡−1(mod25)
22014=2201⋅10+4=(210)201⋅24≡(−1)201⋅24≡9(mod25)
⟹22⋅22014≡22⋅9(mod22⋅25)
No comments:
Post a Comment