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, 6`

and the following rules`0`

, all others are black`k`

to`(k+1)%7`

`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:`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 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.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.