The divisibility test for 3 and 9 is fairly well known. To find out of any given integer is divisible by 9, add up the digits of the number; if the result is divisible by 9 then the number is divisible by 9.
What’s a bit less well known is that in any base b, the same trick applies for b-1 and all of its divisors.
For example, if we are doing arithmetic in hexadecimal (base 16), the divisibility rule we use for base 10 applies not for 3 and 9, but instead for 3, 5, and 15.
Suppose we were to confirm that is divisible by . Adding up the digits:
And since is divisible by , so is the original number.
Let n be an integer, b be the base, and m be the number of digits in n. Then we can represent n:
We can rearrange this:
Each of the expressions , , up to are divisible by . I’ve explored the proof for this in an earlier blog post.
Thus the entire first group of the above expression is divisible by b-1. What remains is the second group, which happens to be the sum of digits in n.
The sum of digits in n is divisible by b-1 if and only if n is divisible by b-1, which is what we wanted to prove.
For a factor of b-1, this also works as the entire first expression is divisible by any factor of b-1.