exupero's blog
RSSApps

Divisibility graphs and modulo tricks

In the previous post we dissected a divisibility graph for 7 that helped calculate the remainder after dividing a multi-digit number by 7, but one can draw such graphs for any number greater than 1, not just 7. Here's the graph for 2:

01

The divisibility graph for 3 is a bit unusual:

012

Each node's white edge loops back to itself. Graphically, it's a nice symmetry, but it also explains the old trick of determining whether a number is divisible by 3 by summing its digits, which always somewhat mystified me. Because each white edge takes you back to your current position on the graph, there's no change in what node you're on when you transition from one digit to the next. Thus, walking the divisibility graph of 3 is the same as simply walking the black edges for each digit, which is the same as summing all the digits, modulo 3.

This reveals a part of the divisibility trick for 3 I've never heard anyone mention. It's usually said that if the sum is divisible by 3, so is the original number, but it turns out whatever the sum's remainder is when divided by 3 is also the remainder of the original number divided by 3.

This trick can be used iteratively. For example, the sum of the digits of 124,759 is 28, whose digits sum to 10, whose digits sum to 1, which is the remainder after dividing 124,759 by 3.

The same features are true of dividing by 9, as evident from its divisibility graph:

012345678

Divisibility graphs also illustrate the ease of finding remainders when dividing by 5 or 10: you only have to look at the last digit because every time you transition from one digit to the next, your position in the graph resets to zero:

01234
0123456789

Here are the graphs for 4, 6, and 8, for completeness; I'm not aware that they reveal any interesting tricks:

0123
012345
01234567

The only other interesting divisibility graph (that I know of) is the one for 11:

012345678910

Subtracting multiples of 11 mirrors you across the graph. Thus, instead of following a white edge every time you transition from one digit to the next, you could think of the black arrows reversing direction and alternate between walking the circle counter-clockwise and clockwise.

This structure explains the slightly bizarre trick for finding the remainder of a number divided by 11: sum every other digit, subtract each digit left out, then find the remainder of the result after it's divided by 11. For example, using the number 234,120,714, add up 2, 4, 2, 7, and 4, then subtract 3, 1, 0, and 1, which produces 14; subtracting multiples of 11 leaves 3. In practice, I find it easier to keep a running total as I alternate between adding and subtracting successive digits:

2-3⇒ -1
+4⇒ 3
-1⇒ 2
+2⇒ 4
-0⇒ 4
+7⇒ 11
-1⇒ 10
+4⇒ 14

And it's this approach that reveals the connection to the above divisibility graph: alternating between adding and subtracting digits is equivalent to reversing direction around the circle with each digit.

Divisibility graphs beyond 11 become unworkably complex:

01234567891011
0123456789101112
012345678910111213
01234567891011121314
0123456789101112131415
012345678910111213141516

There are some interesting designs, and they all have mirror symmetry, but none suggest any divisibility tricks the way 3, 5, 9, 10, and 11 do. Why those particular numbers are special is the subject of the next post.