You might have learned the “divisibility trick” in grade school. It says that if you want to know whether a number is divisible by 3, there is a shortcut: if the sum of its digits is divisible by 3 then the number itself is divisible by 3. For example, is 459 divisible by 3? Well, 4 + 5 + 9 = 18, which is divisible by 3, so 459 is divisible by 3 as well.
This trick also works with the number 9. Again, you can try it with 459.
A week or two ago I was reading Anthony Esolen’s “Word of the Day” blog in which he stated a result about the divisibility trick generalized to a base-X number system; namely, in a base-X number system the divisibility trick works for X-1 and its factors. I was intrigued, and, as I had given some thought to the divisibility trick a few years ago and had some notes on it, I sat down last night and came up with what I think is a sound proof of the claim.
I am sure there is a nice way to formulate the argument — my approach leans heavily on modular arithmetic, which is closely related to the elegant theory of cyclic groups — but I went about it in the most simpleminded way imaginable. You can read my argument here:
DivisibilityTrickBaseX [pdf, Updated]
An amusing application of this result is in a binary (base-2) number system. The claim simply says that any binary number for which the sum of its digits is divisible by 1 (which is all of them, since every positive integer is divisible by 1) is itself divisible by 1 (which is all of them, for the same reason). So the claim is almost empty in that case.