1
$\begingroup$

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

  • 0
    Sorry about that. Seems like the previous notation wasn't an international standard. But it was $[1234567890]_200$ which is the number in base 200 and hence similar once reduced to the modulo.2012-11-14

2 Answers 2

7

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$

  • 0
    @FredericJacobs: this is an extension of checking for divisibility by 2 by checking the last digit, divisibility by 4 by checking the last 2 digits, etc.2012-11-14
1

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$