The graph is the colored directed graph with vertices 0, 1, 2, 3, 4, 5, 6 and the following rules
the white vertex is 0, all others are black
the black arrows connect k to (k+1)%7
the white arrows connect k to (10*k)%7
So each vertex has two outgoing arrows, one black, one white.
If you know the remainder of n modulo 7, this graph allows you to read off the remainders of n+1 and 10*n by following the black and white arrows emanating from the vertex n%7. An integer is divisible if and only if its remainder modulo 7 is 0.
In the example given on the page, you calculate the remainder of 325 as follows:
Start on the white vertex, follow three times a black arrow, then once a white arrow, twice a black arrow, once a white arrow then five times a black arrow and you land on vertex 3 = 325%7.
There’s nothing special about 7 here. Except that it’s the first number for which all divisibility tests in base 10 are kinda tricky, so it’s neat that you can visualize one such test in a planar graph.
You can define similar graphs G(b,m) for every base b>=2 and every modulus m>=1: the set of vertices is {0,...,m-1} and k is connected to (k+1)%m and (b*k)%m for each vertex k. Thus, the graph in the post is G(10,7).
The author lists the planar graphs for small values of b and m in this comment.
Why does this work?
The graph is the colored directed graph with vertices
0, 1, 2, 3, 4, 5, 6and the following rules0, all others are blackkto(k+1)%7kto(10*k)%7So each vertex has two outgoing arrows, one black, one white.
If you know the remainder of
nmodulo7, this graph allows you to read off the remainders ofn+1and10*nby following the black and white arrows emanating from the vertexn%7. An integer is divisible if and only if its remainder modulo7is0.In the example given on the page, you calculate the remainder of
325as follows:325 = ((3 *10 + 2) *10 + 5 = ((0+1+1+1) *10 +1+1) *10 +1+1+1+1+1.Start on the white vertex, follow three times a black arrow, then once a white arrow, twice a black arrow, once a white arrow then five times a black arrow and you land on vertex
3 = 325%7.What makes 7 special? Could I construct a similar graph for 5 or 11?
There’s nothing special about 7 here. Except that it’s the first number for which all divisibility tests in base 10 are kinda tricky, so it’s neat that you can visualize one such test in a planar graph.
You can define similar graphs
G(b,m)for every baseb>=2and every modulusm>=1: the set of vertices is{0,...,m-1}andkis connected to(k+1)%mand(b*k)%mfor each vertexk. Thus, the graph in the post isG(10,7).The author lists the planar graphs for small values of
bandmin this comment.Apparently yes according to this post: https://lobste.rs/s/xnkt8r/techniques_for_factoring_numbers_your
I suspect the author is David Wilson of Wilson’s Algorithm
http://dbwilson.com/
https://en.wikipedia.org/wiki/Loop-erased_random_walk#Uniform_spanning_tree
I didn’t see a graph unless I used a browser without adblock, so the image may be hosted on a network that adblockers don’t like.
must be an odd rule then. no typical ad, analytics etc. keyword in the URL:
Blog is https://blog.tanyakhovanova.com/2009/08/divisibility-by-7-is-a-walk-on-a-graph-by-david-wilson/ Image is http://www.tanyakhovanova.com/BlogStuff/Divisibility7.jpg
Perhaps “visibility” is the culprit?
This could well be. I’m using both Adblock and Ghostery and it’s very possible there’s some weird interaction there.