determine the remainder...?

Question

when 10 123 456 789 876 543 210 is divided by 55.... i have a feeling that i need to use the chinese remainder theorem, but im not 100% sure... please please please show your method, seing as how i already know the correct answer...

Answer 1

I don't see where the Chinese Remainder theorem would fit.

First of all, that long integer is obviously divisible by 5. What's more, it's an easy division, if you divide by 10 first (i.e., lop of the 0) and then multiply by 2.

Now you're down to dividing a long integer by 11. But note that every odd power of 10 is congruent to -1 mod 11, and every even power is congruent to 1 mod 11. So just add up every other digit, and subtract the sum of all the digits you left out, and you'll have the residue mod 11. (The digits that get subtracted are of course the ones corresponding to odd powers of 10.)

That's all it takes.

What's more, if you really understand this method, there's a bit of a shortcut by flipping the order of two steps from what I said above, and instead doing it like this:

1. Divide by 10. (Utterly trivial)
2. Find the residue mod 11. (Easy)
3. Multiply by 2 (Trivial.)

And you're done!