Divisibility

I first became interested in divisibility when I learned that I could test divisibility by 3 or 9 by first adding up all the digits in a number and then testing whether the result was divisible. That seemed like the strangest thing! Naturally I wanted to understand why it worked.

The way I see it now, it's a fact about congruence mod 9. For example,

538 = 5×(99+1) + 3×(9+1) + 8 ≡ 5 + 3 + 8 = 16 mod 9.

Then, since 538 and 16 differ by a multiple of 9, one is divisible by 3 or 9 if and only if the other is.

Once you understand that, you can do the same thing for other divisors. For example,

538 = 5×(98+2) + 38 ≡ 5×2 + 38 = 48 mod 7.

In other words, you can test divisibility by 7 by first grouping the digits in pairs and then doubling each pair and adding it to the next one. Here's how the method works for a larger number, 123456. The part in bold is roughly what your train of thought should be.

12	34	56
24	34	56
	58	56
	116	56
		172

More generally, if you want to test divisibility by m, what you need to do is choose small numbers k and d such that the following equation holds.

10^k ≡ d mod m

Then you can test divisibility by m by grouping the digits in sets of size k and multiplying each set by d before adding it to the next one.

Sometimes there's more than one plausible choice. For example, here's what I consider to be all the possibilities for m = 7.

k	d
1	3
2	2
3	−1
6	1

Now, there's another way to look at the equation above. Instead of fixing m and searching for small numbers k and d, we can do the reverse: enumerate all the useful values of k and d and see for which values of m each one works. And, that's easy. The equation means that 10^k−d is divisible by m, so all we have to do is find the factors of 10^k−d.

The only question, then, is what counts as useful. If we require that the number of digits be at most three, and that the multiplier be at most two, here's what we get.

8 =	23	98 =	2 72	998 =	2 499
9 =	32	99 =	32 11	999 =	33 37
11 =	prime	101 =	prime	1001 =	7 11 13
12 =	22 3	102 =	2 3 17	1002 =	2 3 167

So, for example, because 13 is a factor of 1001, we can test divisibility by 13 by adding digits in sets of three with alternating signs, like so.

123456 = 123×(1001−1) + 456 ≡ −123 + 456 = 333 mod 13

You might recognize many of the numbers above from what I said about fractions (in base N) and other denominators. That's not a coincidence—the fact that a number m divides 10^k−d provides both a way to test divisibility by m and a way to expand the fraction 1/m in a power series. The k = 2 test for divisibility by 7, for example, derives from the same source as the interesting expansion of 1/49. Still, although it's not a coincidence, it does surprise me that the two are related.

There are two more points I need to make, then I'll be able to summarize everything in a table.

First, you can test divisibility by a composite number by splitting the divisor into relatively prime parts. A number is divisible by 21, for example, if and only if it's divisible by 3 and 7. A power of a prime number, however, can't be split, so you need a specific test for each power. If, say, you want to test divisibility by 27, knowing the test for 9 doesn't help, instead you need to know that 27 goes into 999.

Second, the tests for powers of 2 and 5 are special cases. To test divisibility by 4, for example, you only need to look at the last two digits of the number, because 100 is evenly divisible by 4. (In other words, d = 0.)

123456 = 1234×(100+0) + 56 ≡ 56 mod 4

Now, as I said, I can summarize everything. Here are all the useful divisibility tests for small m. The symbol {k,d} represents the test with set size k and multiplier d.

2	last digit
3	{1,1}
4	last two digits
5	last digit
6	check 2 and 3
7	{2,2} or {3,−1}
8	last three digits
9	{1,1}
10	last digit
11	{1,−1} or {2,1}
12	check 3 and 4
13	{3,−1}
14	check 2 and 7
15	check 3 and 5
16	last four digits
17	{2,−2}
18	check 2 and 9

That's a convenient place to stop, since there's no good test for divisibility by 19. (Actually, you can construct one using the fact that 2×10 ≡ 1 mod 19, but it's not the same kind of test as the others.)

That's all I wanted to say about divisibility tests. Now, on to related things!