9s and 3s

At a family get-together over the weekend, we were talking about some curious properties of the numbers 3 and 9. Particularly, that given any number X you can tell whether it is a multiple of 3 or 9 by simply adding the digits in the number, then testing this new number to see whether it is a multiple of 3 or 9. (Apparently, everyone in France knows this rule, which is a little disconcerting.)

So, for example, consider the number 15, is it a multiple of 3 (no guessing!)? First add the digits

1+5 = 6

Then, 6/3 = 2. So yes, its a multiple of 3. No surprises there.

Try a bigger number : 4732938. Add the digits 4+7+3+2+9+3+8 = 36

Since 36/3 = 12, 4732938 is a multiple of 3.

The same thing works for 9. Since 36 is also a multiple of 9, so is 4732938.

Now the obvious question is why does this work? No one seemed to know exactly.

So driving back yesterday afternoon, I thought I'd try and understand why and possibly construct a proof. And it turns out to be quite simple.

The key to understanding the problem is to look at the base under which the number is written. In this case, the base is 10.

We'll start with multiples of 9. Any number X that is a multiple of 9 can be constructed as follows:

X = 9*m, where m is an integer.

Ok, not yet very helpful. Then look at what we're trying to do. A number, written in the base 10 is constructed like this

X = a*10^0 + b*10^1 + c*10^2 + ... + k*10^n

ie a is the units, b is the 10s, c is the hundreds, etc.

The trick is then to write out the equation, substituting 10 as 9+1

X = a*(9+1)^0 + b*(9+1)^1 + c*(9+1)^2 + ... + k*(9+1)^n

Now for the difficult bit.

The terms of the form (9+1)^n can be written as 9*P(n) + 1, where P(n) is a polynomial of degree n. (This is actually easy to prove, but it helps if you have some knowledge of binomials).

Now given this, we can write our equation for X as

X = a*(9*P(0) + 1) + b*(9*P(1) + 1) + c*(9*P(2) + 1) + ... + k*(9*P(n)+1)

And we're almost there. Gather the like terms

X = 9*(a*P(0)+b*P(1)+c*P(2)+..+k*P(n)) + a+b+c+..+k

We said that X = 9*m (if X is a multiple of 9), so if we divide the above equation by 9, each term must be a multiple of 9. The first term clearly is, as theres 9 in front of it. Which leaves us with the last term.

Our condition is then that for X to be a multiple of 9, a+b+c+..+k must be a multiple of 9.

a,b,c, etc are the digits of the number X. So, we've just shown that the sum of the digits must be a multiple of 9: which is precisely the thing we set out to prove!

Whilst the proof might look long, its only actually 3 lines, the rest is just waffle. And its also easy to generalise.

Consider numbers which are multiples of 3. If you go through the above argument, replacing the terms 9+1 with 3^2+1, you arrive at a similar conclusion : that the sum of the digits must be a multiple of 3.

You can also take it still further. The argument suggests (unsurprisingly) that theres nothing remotely special about the numbers 3 and 9. (Sorry for you numerology types). The above property stems from the choice of the number base. In this case, the base 10. If instead of base 10, we wrote our numbers in the base 5, the numbers 2 and 4 would have equivalent properties.

(As a quick check, the number 36 in the base 5, is written as 121.

ie 1*5^2 + 2*5^1 + 1 = 25 + 10 + 1.

Adding the digits, you get 1+2+1 = 4, which is clearly a multiple of both 2 and 4.)

You can also see that the first number basis with a triplet of special values is the base 7. The special numbers would be 2, 3, and 6. (Check : 30 in the base 7 is 42, the sum of which is a multiple of 2, 3 and 6)

So there you have it. The origin of the "add the digits" property.