Little Joys of Discovery #2: A Theorem for Divisibility Tests

You may be familiar with the very simple divisibility test for nines and threes. If you add up the digits of a number, and the sum is a multiple of 9, then the number itself is a multiple of 9. For example, 1+8=9, so both 18 and 81 are divisible by 9. So, too, are 108, 1080, 10000008 and so on. And if the number is so long that the sum of its digits isn't immediately obviously divisible by 9, well, just add up the sum's digits, and there you go.

This is also true of multiples of 3; if the sum of the digits is divisible by 3, then so is the original number.

When I first learned this, I found it interesting, but kind of mysterious. What was so special about the numbers 9 and 3 that they should have this property, and no other numbers should have it? I spent a fair bit of time puzzling over this, and eventually came up with an even more delightful theorem. Again, as with my previous posting on Mersenne primes, I'm likely to be revealing my ignorance of math here to anyone who's actually educated in the subject, but what I'm really trying to share here is how much fun I had figuring this out for myself.

 Here's the insight I had that made it all come together. Whenever you add 9 to something, that's essentially the same as adding 1 to the tens column and subtracting 1 from the units column. So, in principle, since you're adding and subtracting 1, you're not affecting the total.

So let's start with zero. Add 10, subtract 1, you get 9. Do that again, you get 18. And so on, up to 90, which is where it gets a little bit complicated, because you have some digits ticking over and ticking back with the carrying-the-one thing, but ultimately it all works out to the same thing: You're adding 1 to the tens column (turning 90 into 100) and then subtracting 1 from the units column (turning 100 back into 99). Now, the digits add up to 18 instead of 9. But this whole divisibility test is recursive, and you can add 1 and 8 to get 9 again, and there you go.

What happens if you start with one instead of zero? Well, 1+9=10, and 1+0=1, so the sum of the digits remains 1. Add another 9, you get 19, whose digits add up to 10, whose digits again add up to 1. No matter how many times you add 9 (or add 10 and subtract 1), this property will be preserved. More generally, take any number, add up the digits until you're left with just one digit, and whatever that digit is is the remainder when the original number is divided by 9. (Er, sort of. If the remaining digit is 9, then the remainder is zero, but that's because it's impossible to add up any non-zero digits to get a result of zero.)

That's also why the test works for multiples of 3. Any multiple of 9 is, of course, also a multiple of 3, so it's trivially true that if its digits add up to a multiple of 9, it's also a multiple of 3. And if you add 3 to a multiple of 3, the result is also a multiple of 3, so a remainder of 3 (or 6) when a number is divided by 9 indicates divisibility by 3.

When I figured this out, I realized that it's actually part of a more general theorem that works in any base, not just base 10. I'll state it this way:

In any base n, the sum of the digits of any multiple of a factor of (n-1) 

will itself be divisible by that factor of (n-1).

So, for example, in hexadecimal (base 16), any multiple of 3, 5 or 15 will have digits that add up to a multiple of 3, 5 or 15 respectively. 25 in hexadecimal is 19. 1 + 9 = 10 (or in hexadecimal, A) which is divisible by 5. So there. 

This is, of course, well-known to mathematicians and has been for ages. But golly was it satisfying to figure it out for myself!