exupero's blog
RSSApps

Divisibility graph for 7

I encountered David Wilson's divisibility graph for 7 some time ago, presented as a visual graph-walking method for finding the remainder of a number after it's divided by 7. Here's my recreation of David's graph:

0123456

The nodes each have two outgoing edges, one with a black arrow and one with white. To use the graph, have a number to find the remainder of, start at zero on the graph, then traverse as many black-arrowed edges as the first digit followed by one white-arrowed edge. Repeat these black/white traversals for each remaining digit except the last; for the last digit, only traverse black-arrowed edges. The number you end up on is the remainder when dividing by seven.

As a worked example, consider the number 1,642.

  1. Start on 0.
  2. Walk 1 black edge to node 1.
  3. Walk the white edge to 3.
  4. Walk 6 black edges to 2.
  5. Walk the white edge to 6.
  6. Walk 4 black edges to 3.
  7. Walk the white edge to 2.
  8. Walk 2 black edges to 4.

The remainder of 1,642 divided by 7 is indeed 4.

Such a graph walk works by incrementally subtracting multiples of seven and continuing with only the remainder. Walking the white edge from 1 to 3 is a subtraction of 7 from 10. Following 6 black edges from 3 takes us to 9, but the circle implicitly subtracts 7, leaving 2. The white edge from 2 to 6 subtracts 14 from 20. Four black edges from 6 to 3 again subtracts a 7. The white edge from 3 to 2 subtracts 28 from 30. Two black edges from 2 is 4, our answer.

Or, stated symbolically,

While it's clever to illustrate these operations as a graph, I haven't found it useful for mental calculations. It's much easier to subtract multiples of seven than to decompose numbers by magnitude and subtract multiples of seven. For example, the first two bullets above can be done in a single quick step by subtracting 1400 from 1642, the next two by subtracting 210 from 242, and no difficult calculations need to be done to know that the remainder of 32 divided by 7 is 4.

But this approach does provide some insight into a couple modulo tricks, which we'll look at in the next post.