## Monday, March 16, 2020

### Blog: So Why Does The Divisibility Test for Nine Work?

I've been reading another old math book. This one is Mathematical Puzzles and Pastimes by D. Van Nostrand, Inc.,(1954). As best as I can tell, the author's initial's are A.B.

A review or two will be forthcoming in the days ahead. I won't be breaking it down by chapters as I did with the last one. Two blog posts will probably do fine.

### Why Does the Divisibility Test For 9 Work?

There's an interesting chapter on "GOESINTOS", as in divisibility by. I'll put the notation aside and use a concrete example. I like examples first, and then general rules after.

Let's take a number like 2,467. We know that it is divisible by 9 because 2 + 4 + 6 + 7 = 18 and 1 + 8 = 9. (For that matter, we know that 18 is divisible by 9.)

But why should this matter?

Note: I touched upon this in a blog post about dividing polynomials by (x - 1), but I didn't think about the sum of the digits because I was using variables. So close!

The answer lies in writing the number out in expanded notation:

2 * 103 + 4 * 102 + 6 * 101 + 7 * 100

This can be rewritten as:

2 * (9 + 1)3 + 4 * (9 + 1)2 + 6 * (9 + 1)1 + 7

We can leave off the 0 power exponent, since it equals 1.

If we do the binomial expansion, it gets a little crazy, and I start to regret using a four-digit example. But here goes:

2 * (93 + (3)9211 + (3)9112 + 13)
+ 4 * (92 + (2)9111 + 12)
+ 6 * (91 + 11)
+ 7

This in turn becomes:

(2)(93) + (2)(3)(92) + (2)(3)(91) + (2)(1)
+ (4)(92) + (4)(2)(91) + (4)(1)
+ (6)(91) + (6)(1)
+ 7

If we regroup the terms, we can put all the terms with factors of 9 up front:

(2)(93) + (2)(3)(92) + (2)(3)(91) + (4)(92) + (4)(2)(91) + (6)(91) + (2) + (4) + (6) + 7

Finally, we'll factor out a 9 from those initial terms:

9[(2)(92) + (2)(3)(9) + (2)(3) + (4)(9) + (4)(2) + (6)(9)] + [(2) + (4) + (6) + 7]

The sum of the original digits are being added to a multiple of 9. So the only way for the original number to be divisible by 9, is if 2 + 4 + 6 + 7 adds up to a multiple of 9. Adding one multiple of 9 to another multiple of 9 will yield a sum that is also a multiple of 9:

9 * M + 9 * N = 9(M + N)

Okay, so I said that I would prove it in general now. Well, I lied. I could, but I'm not going to because it's a bit repetitious for a blog.

Replace my digits with A, B, C, D, and you will get the same result for the sum of A + B + C + D, proving it for any four-digit number.

Replace them with a1 + a2 + ... + an, and you can prove it for any number of digits. But that requires me to code subscripts and use the Combination notation (with more subscripts to code).

However, this is also the part where I get to say:

### BUT WAIT! THERE'S MORE!!

It's not just Nines!

In fact, if you replaces the 10s with "B" (which stands for Base, which rhymes with Your Face!), you will see that (B - 1) can always be factored out.

Let's use the above example again:

2 * ((B - 1) + 1)3 + 4 * ((B - 1) + 1)2 + 6 * ((B - 1) + 1)1 + 7

Applying the same steps would lead to:

(B - 1)[(2)((B - 1)2) + (2)(3)(B - 1) + (2)(3) + (4)(B - 1) + (4)(2) + (6)(B - 1)] + [(2) + (4) + (6) + 7]

This means that if 2,467 is in base 9, we could tell if it were divisible by 8. If it were it base 8, we could tell if it were divisible by 7. Use smaller digits, and we could check base 6, 5, or 4 if we wanted to.

Do you want to? It will give you something to work out this afternoon.