To find last two digits of $2^{100}$
I have just learned about modular arithmetic and I wanted to solve this problem. I only know about equivalence classes and about $a=b \pmod n$. I have also learned about multiplication and addition of classes. Can someone explain to me step by step on how to apply modular arithmetic to this problem?
Thanks
Best Answer
Method 1(using fast power algorithm):
$2^0 \equiv 1 \pmod {100}$
$2^1 \equiv 2 \pmod {100}$
$2^2 \equiv 4 \pmod {100}$
$2^4 \equiv 16 \pmod {100}$
$2^8 \equiv 56 \pmod {100}$
$2^{16} \equiv 36 \pmod {100}$
$2^{32} \equiv 96 \pmod {100}$
$2^{64} \equiv 16 \pmod {100}$
Since $100 = 4 + 32 + 64$
$2^{100} \equiv 2^{4} 2^{32} 2^{64}\equiv 16 \times 96 \times 16 \equiv 76 \pmod {100}$
Method 2(using minimal cycle to improve):
Since $2^{22} \equiv 4 \pmod {100}$, $2^{100} \equiv 2^{22 \times 4 + 12} \equiv 4^4 \times 2^{12} \equiv 2^{20} \equiv 16 \times 96 \equiv 76 \pmod{100} $
Last but not least: Since $2^{20} \equiv 76 \pmod {100}$, $76 \times 76 \equiv 76 \pmod{100}$, $2^{100} = 2^{20 \times 5} \equiv 76^5 \equiv 76 \pmod{100} $ by induction.