Question

Im struggling with modulo arithmetic.

How would i calculate 3^100 mod 1000

Answer 1

\(\large \begin{align} \color{black}{
\normalsize \text{the shortest way would be to use binomial theorm} \hspace{.33em}\\~\\
3^{100} \pmod {1000} \hspace{.33em}\\~\\
=9^{50} \pmod {1000} \hspace{.33em}\\~\\
=(-1+10)^{50} \pmod {1000} \hspace{.33em}\\~\\
=\dbinom{50}{0}\cdot (-1)^{50}\cdot (10)^{0}+\dbinom{50}{1}\cdot (-1)^{49}\cdot (10)^{1}\hspace{.33em}\\~\\
+\dbinom{50}{2}\cdot (-1)^{48}\cdot (10)^{2}+ \color{red}{\dbinom{50}{3}\cdot (-1)^{47}\cdot (10)^{3}\cdot \cdot \cdot } \pmod {1000} \hspace{.33em}\\~\\
\normalsize \text{note :-(starting from red terms all will be) } \equiv 0 \pmod {1000} \hspace{.33em}\\~\\
=1+50\cdot (-1)\cdot (10)^{1} +\dfrac{50\times 49}{2}\cdot 1\cdot 100 \hspace{.33em}\\~\\
+ \color{red}{0+0+0\cdot \cdot \cdot } \pmod {1000} \hspace{.33em}\\~\\
=1-500
+2500\times 49 \pmod {1000} \hspace{.33em}\\~\\
=1-500
+500\times (50-1) \pmod {1000} \hspace{.33em}\\~\\
=1-500
+25000-500 \pmod {1000} \hspace{.33em}\\~\\
=1 \pmod {1000} \hspace{.33em}\\~\\
=1 \hspace{.33em}\\~\\
}\end{align}\)