Modulo Prime Powers

Lesson · Intermediate

Number Theory

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=-99\equiv26\pmod{125}

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