Saturday 16 February 2013

Casting out nines, or almost any other number

I have always had an interest in the divisibility tests, and particularly the old method called "Casting out nines". Most people of my extended age learned it as a way of checking arithmetic work when they were in elementary or middle school. The idea was that if you add the digits of any decimal number, the result had the same remainder on division by nine as the original number. If you divide 321547 by nine, the remainder will be four. I know that because if you add the digits 3+2+1+5+4+7 the total is 22 and 22 has a remainder of 4 when you divide by nine. This remainder is called the digital root of the number; so 4, 13, 22, 321547 all have the same digital root. The more advanced language of number theory would call these numbers "congruent modulo nine" , but we shall stick with digital root.
The utility of the process was that if you add, subtract or multiply two numbers, the sum or product produced will have the same digit root as the sum or product of the digital roots of the numbers in the problem. If you multiply 23 (with digital root 5) times 47 (with digital root 2), you would get a number that has a digital root of 1.  The name casting out nines probably comes from the fact that you can simplify the work by simply crossing out any nines, or even pairs of numbers that sum to nine.  In the image at top they show that 17,999 has a digital root of 8, which is much easier to see if you just cross out the three nines in the first place. In much the same way you can quicken the 42,572 by crossing out the 7 and 2 (one nine) and also the 4 and 5 (another nine) and only a single 2 is left.

I have played around with other divisibility rules, and even made up some of my own. If you want to read these early blogs first, you might try this one, or another here.

The reason I am reminded of all this is that I just read an interesting article by the almost unknown English mathematician, Henry Wilbraham (July 25, 1825 – February 13, 1883), in an old Cambridge and Dublin Mathematical Journal. He points out that you can construct a similar division technique for any number. The idea is to use the period of the smaller numbers repeating fraction to break apart the second number. As an example, if you wanted to test to see if some large number was divisible by 37, you would first find the digital period length of the decimal 1/37. It turns out that 1/37 = 0.02702702702702703 so its period is three.
Now we take the really big number we want to test, say 7,424,883,933,621. We want to know if that number is evenly divisible by 37, and if it isn't, what the remainder will be.
The variation in Wilbraham's approach, and as I point out later it's not really an a variation at all, is to break the larger number up into sections of three digits (the period of our divisor's reciprocal), so we would add the 621+933+883+424+7= 2868. Now just as we can continue to compute digital roots when casting out nines, because there are more than three digits here, we can recombine those to get 2+868 = 870. Now all we have to do is divide 37 into 870 and if it goes evenly, it's a factor of the larger 13 digit number. If not, the remainder we get will be the same as the remainder when dividing the original number.
Turns out 37 is not a factor of 870 but leaves a remainder of 19. The good news is that we know that when we divide 7,424,883,933,621 by 37, we will get the same remainder.

It turns out that the reason this works is the same as the reason that casting out nines works. The period of 1/9 is one,.11111....., so we add every digit.

The math behind this is simple enough that I think any bright high school kid could understand it. If the period of a numbers reciprocal 1/n is some number p, then it must be true that 10p-1 is divisible by n. In my example, 103-1 must be divisible by 37, and is.
So if we break our larger number, N, up into periods of p, and express the sets of digits as individual numbers, A,B,C,D... so that N= A+10pB + 102p...etc.
So we know that N= A+ (kn+1)B+ (kn+1)2 C.... and if we distribute all these kn+1 terms all the kn powers can be collected (and are thus a multiple of our smaller divisor, n) and the rest will be A+B+C... which is the sum of the periods, and thus the remainder. If this number is longer than the period of 1/n, we can apply it again by using the same reasoning.

I should point out, because Wilbraham is so unknown, he did not spend his entire mathematical life doing arithmetic novelties. He is known for discovering and explaining the Gibbs phenomenon, the peculiar manner in which the Fourier series of a piecewise continuously differentiable periodic function behaves at a jump discontinuity, nearly fifty years before J. Willard Gibbs did. Gibbs and Maxime BĂ´cher, as well as nearly everyone else, were unaware of Wilbraham's work on the Gibbs phenomenon.

No comments: