Thursday, January 3, 2013

Casting out nines.

Number theory is the study of the properties of whole numbers. Divisibility and primes are the major part of the field. It is usually counted as part of pure mathematics, the study of the discipline that is done for its own sake and for the sake of beauty, but even the most esoteric parts of math sometimes have practical purposes.

On New Year's Day, I discussed how to determine if a number is divisible by 3. The "trick" or method is to add up the digits. If that sum is divisible by 3, so is the original number, If it's not divisible by 3, the original number isn't divisible by 3 either.

The method for divisibility by 9 is very similar. Add the digits and check to see if the sum is divisible by 9. If yes, the original number is divisible by 9, and if no, the original number is not divisible by 9.

For example, the number of feet in a mile is 5,280. 5+2+8+0 = 15, which is divisible by 3 but not divisible by 9. The prime factorization of 5,280 is 2 × 2 × 2 × 2 × 3 × 5 × 11. For a number to be divisible by 9, we need two copies of 3 in the prime factorization,

And now for the practical use. In the 19th Century, there were no calculators and people did all their computations by hand. For example, clerks and accountants spent much of their days adding long columns of numbers. Let's set up a small example.

322.75
201.43
75.32
+835.85

The correct answer is 1435.35. But let's say a weary clerk makes a mistake and only carries 1 when adding up the tenths column instead of carrying 2. The answer would become 1434.35 and would be incorrect.

What we are going to do is add the digits of each of the numbers together. To take the process a step further, if the sum is two digits long we will add the digits together to get a one digit number.

322.75 -> 3+2+2+7+5 = 19 -> 1+9 = 10 -> 1+0 = 1
201.43 -> 2+0+1+4+3 = 10 -> 1+0 = 1
75.32 -> 7+5+3+2 = 17 -> 1+7 = 8
835.85 -> 8+3+5+8+5 = 29 -> 2+9 = 11 -> 1+1 = 2

Notice that 19 gets sent to 1, just as 10 is sent to 1, and 29 is sent to 2. Anytime a 9 shows up in our calculations, it acts on the sum just as if it were 0, not changing the sum at all. If you do this a lot, it's easy to see that a 9 can be thrown out, which gave the method the name "casting out nines".

Okay, so now the sum we have is 1+1+8+2 = 12, which we can break down further to 1+2 = 3.  What good is it?

The answer we get when adding up all the numbers should also become 3 when we cast out nines. The correct answer of 1435.35 becomes 1+4+3+5+3+5 = 21 and 2+1 = 3. When I made the mistake in carrying, I got 1434.35, which becomes 1+4+3+4+3+5 = 20 and 2+0 = 2. This was a relatively easy way to check for mistakes in sums.

Casting out nines is not perfect. The simple mistake of transposition of numbers will not be caught. For example, let's say I wrote 210.43 instead of 201.43 for the second number in the list.

322.75
210.43
75.32
+835.85
1444.35

1,444.35 becomes 1+4+4+4+3+5 = 21 becomes 2+1 = 3. When casting out nines, it is not distinguishable from 1,435.35.  Another method is needed to catch transpositions and it went under the name casting out elevens. We will take a look at this tomorrow.