Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  fred Nov 14 '12 at 15:10
add comment

2 Answers

up vote 7 down vote accepted

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$

share|improve this answer
    
Right. Thanks ! That was the simplification I was looking for. –  fred 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
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.