Just a quick diversion:

I was interested by this post http://blog.tanyakhovanova.com/?p=262, which shows how walking a graph can perform a modulo operation. The author lists the procedure:

"To find the remainder on dividing a number by 7, start at node 0, for each digit D of the number, move along D black arrows (for digit 0 do not move at all), and as you pass from one digit to the next, move along a single white arrow."

It is easy to see how to construct a graph for this to work: for each digit, black arrows points to its successor and white arrows point to the value (10*r % m), where r is the current value and m is the divisor. This works because incrementing a number also increments its value modulo m, and advancing a digit (multiplying by 10) changes the modulo to (10*r % m).

The concept of divisibility graphs can be generalized to any number in this way. A specific subset of these graphs that I found interesting is binary divisibility graphs: the same concept, but in base 2. A binary divisibility graph could be traversed as a finite-state-machine, to compute the modulo operation in linear time (linear in number of binary digits).

Here are some examples. To traverse these, start at the 0 node, and begin with the leftmost binary digit (MSB). If the next digit is a 0, traverse the black edge. If it is a 1, traverse the red edge. The terminal node is the value of the number modulo the divisor.

Binary Mod 4:

Binary Mod 10

Binary Mod 100