11 and more...

For those that have seen the previous blogs, you'll know that I've been talking about ways of computing factors of numbers. Everything I've talked about is related to the fact that you can sum the digits of numbers, and find out whether the original number is a multiple of 9 (or 3). I also showed that you can use a similar method to show whether any number is a factor of another.

But what I hadn't thought about (though nothing precluded it), is what happens when the factor is greater than the base number.

For example, before we talked about numbers which were multiples of 9. But what about 11, which is 1 greater than the base?

Well, it turns out that that works too!

Remember that the constraint is that

a + b*r^1 + c*r^2 + .. + k*r^n

be a multiple of f - the factor we're looking for.

Now, originally I'd imagined that f was less than than the base value (ie <10) giving a positive remainder r. But it still works for negative r.

The simplest case is that of the numbers which are multiples of 11, which gives remainder of -1. Pluging in r=-1 into the above equation, you see that the equation for 11ssss reduces to

a - b + c - d + ...

ie you just alternatively add and subtract the digits of the original number (going from right to left), then check to see whether the answer is a multiple of 11 or not.

One thing to be aware of is that the sum can equal 0. Which implies that its a multiple of 11, as in the case of 121 (+1-2+1 = 0).

addendum of 3 and 9

From the previous post, its easy to get the impression that there is only one rule that works, ie the sum of the digits being a multiple of 3 and 9. But if you look carefully, you'll see that in fact there are quite a number of rules. In fact, theres a rule for every digit.

The most important part of the proof lies in the separation of the base (in this case 10), into 2 parts. To be more concrete, we were interested in the numbers that were factors of 9 (or 3), so we constructed the proof by separating the factor from the basis, by converting 10 into 9+1. But what happens if we want to know whether a number is (for example) a multiple of 7?

Wait a minute, lets get general.

Lets call the base z and the factor we're interested in to be f. The crucial bit we'll be interested in is r = z-f. So, with these definitions, we can construct the more general equation to represent our number X, we get:

X = a*(f+r)^0 + b*(f+r)^1 + b*(f+r)^2 + ....+ k*(f+r)^n

If we once again expand the power terms, we can write the equation as

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

Collecting the like terms, we have:

X = G + (a + b*r^1 + c*r^2 + ... + k*r^n)

Now, for the same reasons as before f is guaranteed to be a factor of G, which leaves us with the terms in brackets. So for X to be a multiple of f, f must be a factor of :

a + b*r^1 + c*r^2 + ... + k*r^n

At this point you might be thinking I've gone mad. So lets recap.

r is the remainder left after taking the factor we're interested in, f, away from the base.

So, before we were interested in factor 9 (in base 10) which gives a remainder r = 10-9 = 1

Our requirement is then that

a + b*1 + c*1 + .. + k*1 = a + b +c + .. + n

be a multiple of f. Which as every french person knows, is the original formula.

But what about 7?

To find numbers which are multiples of 7 (using this formula), we need to do the following

First, calculate r...

Well, r = 10 - 7 = 3

So, for 7 to be a factor of X, then

a + b*3 + c* 3^2 + ...+ k*3^n

must be a multiple of 7.

Lets check : is 63 a multiple of 7?

Using the equation we get 3 + 6*3 = 21. 21 is a multiple of 7, therefore so is 63.

The equation shown above will work for any number, under any basis.

Of course, that doesn't make it useful. The power of the known "sum the digits" rule stems from its simplicity. Because the remainder, r, is 1. After that, it becomes so complicated to perform the calculation that you may as well have done the actual division!

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.