# Fastest way to compute [1234567890]_200 with pen and paper

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 don't know why you deleted the information that you wanted the remainder and would ask you to roll back. I don't recognize the notation and wouldn't have known what you wanted. Some guidance on $\LaTeX$ is here I got what you see with 890 \pmod {200} enclosed in dollar signs. – Ross Millikan Nov 14 '12 at 15:05
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. – BrainOverfl0w Nov 14 '12 at 15:10

## 2 Answers

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$

-
Right. Thanks ! That was the simplification I was looking for. – BrainOverfl0w Nov 14 '12 at 15:02
@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. – Ross Millikan Nov 14 '12 at 15:09

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$

-