Divisibility diagrams

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".