Let f be the function defined by f(i,d) = (10 * i + d) mod n, that is, the remainder of 10*i+d after division by n.

Read the number, digit by digit, remembering at every step the remainder r of the number after division by n.
We can do this by moving from r to f(r,d) on reading a digit d!

This means that we can do it using a finite state automaton.

For details and proof, see ariels's writeup on the case n=17.

Log in or register to write something here or to contact authors.