1. 18

  2. 4

    Why does this work?

    1. 13

      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:

      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.

      1. 3

        What makes 7 special? Could I construct a similar graph for 5 or 11?

        1. 5

          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.

          1. 1
      2. 2

        I suspect the author is David Wilson of Wilson’s Algorithm



        1. 1

          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.

          1. 3
            1. 2

              Perhaps “visibility” is the culprit?

              1. 1

                This could well be. I’m using both Adblock and Ghostery and it’s very possible there’s some weird interaction there.