Eliminating Your Footprints

When last we discussed divisibility rules, particularly, rules for just adding up the digits in a number to tell what it might divide by, we had worked out rules for testing divisibility by eight. In that, we take the sum of four times the hundreds digit, plus two times the tens digit, plus the units digit, and if that sum is divisible by eight, then so was the original number. This hasn’t got the slick, smooth memorability of the rules for three and nine — just add all the numbers up — or the simplicity of checking for divisibility by ten, five, or two — just look at the last digit — but it’s not a complicated rule either.

Still, we came at it through an experimental method, fiddling around with possible rules until we found one which seemed to work. It seemed to work, and since we found out there are only a thousand possible cases to consider we can check that it works in every one of those cases. That’s tiresome to do, but functions, and it’s a legitimate way of forming mathematical rules. Quite a number of proofs amount to dividing a problem into several different cases and show that whatever we mean to prove is so in each ase.

Let’s see what we can do to tidy up the proof, though, and see if we can make it work without having to test out so many cases. We can, or I’d have been foolish to start this essay rather than another; along the way, though, we can remove the traces that show the experimenting that lead to the technique. We can put forth the cleaned-up reasoning and look all the more clever because it isn’t so obvious how we got there. This is another common property of proofs; the most attractive or elegant method of presenting them can leave the reader wondering how it was ever imagined.

A number up to a thousand we can write as cba, with each of those letters one of the ordinary digits. We don’t have to worry about numbers bigger than a thousand, since they’re some multiple of a thousand plus cba, and we know a thousand is divisible by eight, so any number of thousands plus cba can be divided by eight only if cba is. And we know that cba is c times a hundred plus b times ten plus c times one.

We remember from the rules about dividing by three and by nine that we got much done by rewriting the base of our number system as a multiple of three or nine plus a remainder. That trick worked once; why not try it again? Ten is eight plus two; a hundred is … here we have to look through the times tables some, but a hundred is ninety-six (twelve times eight) plus four. So now let’s look at cba again.

c hundreds is eight times twelve times c plus four times c. b tens is eight b plus two b. a ones is just a. So, cba is eight times twelve times c plus eight times b plus four times c plus two times b plus a. And all that eight times stuff is irrelevant to the divisibility by eight. All that could possibly not be divisible by eight is the sum four times c plus two times b plus a. And this is exactly the rule we had worked out.

If we felt ambitious we might point out that we could claim we were following the same rule for the thousands column: 1000 times d, our thousands-column number, is eight times 125 times d plus zero times d. So the calculation to be done to test whether dcba is divisible by eight is zero times d plus four c plus two b plus one a. The same reasoning extends to the ten-thousands, and the hundred-thousands, and millions, and further columns.

Now we’re starting to get what might be a general rule. If we want to test whether a number is divisible by some other number, let’s say B so it has some non-awkward name, we need to look at what’s left over when ten is divided by B, when a hundred is divided by B, when a thousand is, and so on. And we take the sums of those remainders times the digit in those columns to build the smaller number that we check.

Looking back, this is exactly what we were doing all along: every multiple of ten, divided by either three or nine, gives a remainder of one, and we test divisibility by three or nine by taking one times every digit and adding that up. Divisibility by eight we developed in the last essay on this subject, and we just proved out above. For multiples of four, well, ten is two more than a multiple of four; a hundred is exactly a multiple of four, and all the higher powers of ten are also multiples of four. So our rule should be two times the tens column plus the ones column and, yes, that works. We could test all the numbers between zero and 100 to check, or we’d probably actually just see that 12 and 24 both follow that rule and say that’s testing enough cases.

Two and five divide evenly into ten; so, to test divisibility by two or five only the last digit, the ones column, has to be considered. And we know that’s so. Similarly for multiples of ten, we only have to see whether there’s a zero in the ones column.

Now we have a procedure that not only works, but one that shows us why it should work, and one that lets us figure out this weighted-digit-addition rule to work out divisibility by any base.