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!