I'm wondering if there is a more elegant and faster way to compute $1234567890 \bmod 200$ with pen and paper than doing the arithmetic division.
Thanks
I'm wondering if there is a more elegant and faster way to compute $1234567890 \bmod 200$ with pen and paper than doing the arithmetic division.
Thanks
Since $1000$ is divisible by $200$, you can ignore all the leading digits and compute $890 \pmod {200}$ Then long division is easy, giving $90$
Note for integers $\rm\:a, b,\ $ if $\rm\:a\mid b\:$ then $\rm\:ab^2\mid \color{#0A0}{b^3,b^4,\,\ldots},\, $ hence in radix $\rm b\:$ notation
$\begin{eqnarray}\rm\qquad\ \ mod\ ab^2\!:\quad\ &&\rm d_0 +\ d_1 b\, +\: d_2 b^2 +\, \color{#0A0}{b^3\, (\cdots)}\\ \equiv &&\rm d_0 +\ d_1 b\, + (\color{#C00}{d_2\, mod\ a)\, b^2}\ \ \ by\ \ \ d_2b^2 = (aq+r)\,b^2\equiv\, \color{#C00}{ r\,b^2}\\ \end{eqnarray}$
So $\rm\:mod\ 2\cdot 10^2\!:\ \ldots \color{#C00}cba\, \equiv\, \color{#C00}{\bar c}ba\ \,$ where $\rm\,\ \color{#C00}{\bar c} = (\color{#C00}c\ mod\ 2)$
So $\rm\:mod\ 2\cdot 10^2\!:\ \ldots \color{#C00}890\, \equiv\, \color{#C00}090$