Suppose you want to work out the remainder on dividing a number by *N*.
The answer is a number in the range *0* to *N-1*. Hold on to that thought.

Suppose you've got a number, say 3245. That's *3×1000 + 2×100 + 4×10 + 5×1*.
Another way of writing it is *10×(10×(10×(3) + 2) + 4) + 5*.

If you only know how to interpret single digits and not multi-digit numbers, you could work out what "3245" means by performing that calculation - start with 0, and for each digit, multiply what you've got by 10 and then add the digit.

It's easy to work out the remainder of a small number modulo *N*, but hard to do it with a very long number.

You can use the method above, but at the end of each step swap the number you've got with its remainder on dividing by *N*. So you've always got a number between *0* and *N-1*, and once you've dealt with every digit, you'll have the remainder on dividing by *N*!

The hard part in this process is working out the remainder on dividing *10×k* by *N*. But there are only *N* different values of *k*, so work them out in advance!

This tool draws a diagram which does the work for you: the dotted blue lines represent the "multiply by 10" step, and the green arrows represent "adding 1".