In the figure displayed in the image below :
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.
For example, let $n = 325$. Start at node $0$, move along $3$ black arrows (to node $3$), then $1$ white arrow (to node $2$), then $2$ black arrows (to node $4$), then $1$ white arrow (to node $5$), and finally $5$ black arrows (to node $3$). Finishing at node $3$ shows that the remainder on dividing $325$ by $7$ is $3$.
If you try this for a number that is divisible by $7$, say $63$, you will always end up in node $0$. Therefore, it can also be used to test divisibility by $7$. In case while traversing the digits of number $n$, you end up in the node $0$, $n$ is divisible by $7$, else not.
What exactly is the mathematical explanation for this? Are there such type of graphs for any other integer(s) too?
Best Answer
Such graphs exist for any (non-zero) integer. In fact, the arrows reflect two basic operations $\bmod 7$:
Any given number can be written as a combination of these two operations on a starting value of zero; for instance, your example $N=325$ is equivalent to starting with zero, adding $1$ three times (giving $3$), multiplying by $10$ (giving $30$), adding $1$ twice more (giving $32$), multiplying by $10$ again (giving $320$), and then adding $1$ five more times (giving $325$). The graph just represents these operations $\bmod 7$, and so if you end up at node zero it means that your original number was a multiple of 7; this works because both the operations of adding one and multiplying by ten 'commute' through the mod-7 operation (i.e., $(n+1)\bmod 7$ $\equiv (n\bmod 7)+1\pmod 7$ and $(n\times10)\bmod 7$ $\equiv (n\bmod 7)\times 10\pmod 7$ ). Since the individual operations commute with the mod operation, so will any combination of them.
But there's nothing special about $7$ here, and in fact that's enough to understand how to construct the graph for any base $b$: number a set of $b$ nodes from $0$ to $b-1$, and then construct a black arrow from $i$ to $i+1\pmod b$ for every node $i$, and a white arrow from $j$ to $j\times10\pmod b$ for every node $j$. This will give the analogue of the 'Mickey Mouse' graph for that base.