Toolkit 118: Solving Modulo Prime Powers (Binomial Expansion Method)

2^{341}\equiv ?\pmod{125}

125=5^3

2^{341}=2\cdot2^{340}=2\cdot4^{170}=2(5-1)^{170}

(5-1)^{170}=\binom{170}{0}-\binom{170}{1}5+\binom{170}{2}5^2-\binom{170}{3}5^3+\binom{170}{4}5^4+\cdots

\equiv \binom{170}{0}-\binom{170}{1}5+\binom{170}{2}5^2\pmod{125}

=1-170\cdot5+\frac{170\cdot169}{2}\cdot5^2

\equiv1-850+85\cdot169\cdot5^2\pmod{125}

\equiv1-850\pmod{125}

\equiv1-100\equiv-99\equiv26\pmod{125}

2^{341}=2\cdot26\equiv52\pmod{125}