exupero's blog
RSSApps

Divisibility scatter plots

In a previous post I showed some divisibility graphs for base-10 numbers greater than 11, such as this one for 12:

01234567891011

As already discussed, divisibility graphs are interesting but not very useful for mental calculations. Even if they were, the graphs for bigger numbers rapidly become too complex to memorize, and it's the bigger numbers for which we need help when taking modulos.

The white arrows calculate bi mod n (where b is the base, i is the number in the red circle, and n is the number whose modulo we're finding), but instead of illustrating it as a walkable graph, we can illustrate it as a scatter plot in which y = bx mod n. That is, a plot with the white edges' starting points as x-coordinates and ending points as y-coordinate. Here's the scatter plot for 12:

0123456789101101234567891011

A pattern is clearer now: a line with negative slope wraps around the graph from bottom to top. The slope of -2 happens because 12 is two more than 10 and each successive multiple of 10 has two more taken from it by successive multiples of 12. We can exploit this behavior to calculate 10i mod 12 more easily with -2i mod 12.

By a similar pattern, modulo 13 can be calculated with -3i mod 13:

01234567891011120123456789101112

The pattern continues, of course, though scatter plots begin to suggest an alternative strategy For example, here's the plot for 14:

012345678910111213012345678910111213

Lines of slope -4 are still present, but the spacing of the points makes it harder to see. Instead, we start to notice the points that are closer together and form lines with a positive slope of 2/3. While this line forms as a bit of an optical illusion, it reflects the fact that for each successive multiple of 30, modulo 14 leaves two more (instead of taking two more like modulo 12 did).

Using this observation is a bit trickier than just multiplying by -2. Now we have to multiply by 2 and divide by 3. But this only works for numbers where 2i mod 3 = 0, since if we divide a number that's not evenly divisibly by 3 by 3, we'll end up with a fraction, and a fraction can never be the remainder after dividing a whole number by a whole number.

To find a workaround, we can extend the plot:

0123456789101112131415161718192021222324252627012345678910111213

Notice how the 2/3-slope line continues into the shaded area, then wraps around to the bottom at (21, 0):

0123456789101112131415161718192021222324252627012345678910111213

The point above 15 represents adding 14 to 1, and 15's double is evenly divisible by 3, giving 10. To find results for 2, 5, 8, etc., we can subtract 14:

-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456789101112131415161718192021222324252627012345678910111213

Two minus 14 is -12, whose double is -24, whose third is -8, whose modulo 14 is 6. Of course, in the case of 2, it's easier to find 20 mod 14, but it may be easier to mentally calculate, say, 50 mod 14 with (5 - 14)×2÷3 mod 14, which doesn't require multiplication of any large numbers.

Working out modulos this way takes some practice and memorization of different patterns. If you find yourself occasionally factoring numbers, you can limit your memorization to primes, whose slopes are a bit easier to remember. See if you can identify the pattern:

17:

012345678910111213141516012345678910111213141516

19:

01234567891011121314151617180123456789101112131415161718

23:

012345678910111213141516171819202122012345678910111213141516171819202122

29:

012345678910111213141516171819202122232425262728012345678910111213141516171819202122232425262728

31:

01234567891011121314151617181920212223242526272829300123456789101112131415161718192021222324252627282930

In each case, the slope's run is equal to a tenth of the nearest multiple of 10: 17, 19, and 23 all have a slope with a run of 2; 29 and 31 have a run of 3; etc. The rise on each slope is equal to the difference between the number and that same multiple of 10: 17 has a rise of 3, 19 has a rise of 1, 23 has a rise of -3, 29 has a rise of 1, 31 has a rise of -1, etc.