1

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

BrainOverfl0w
  • 197
  • 8
  • 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 Answers2

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$

Ross Millikan
  • 374,822
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$

Bill Dubuque
  • 272,048