Monday, December 30, 2013

Casting Out Mathematical Demons

Casting Out Mathematical Demons

By Bobby Neal Winters
The other day on his Word of the Day blog, Anthony Esolen made reference to the divisibility test for 9 and 3.  The basic idea is this: take the base 10 expression of a number and add up its digits.  That is called the digit sum/ mathematicians don’t waste their imagination on names for things.  If the digit sum is divisible by 9 (or by 3) then the original number was.  
For example, 5643 is divisible by 9 because 5+6+4+3 is 18 and 18 is divisible by 9.  If you aren’t good enough at arithmetic to know that 18 is divisible by 9, note that 1+8=9.  If you don’t know that 9 is divisible by 9, then I can’t help you.  
There is a name for this beyond the Division Test for Divisibility by 9.  It’s called Casting Out Nines.  The reason for this name might become apparent after you’ve done a lot of testing.  Say that you have a number 9954968 and you want to determine whether 9 divides it.  You only need to calculate 5+4+6+8 because those 9s will not add any information and will only add complication to the addition,  so you cast them out.  Indeed, as that 5+4 is a pat 9, you can leave them out too and only worry about the 6+8=17 which is not divisible by 9.
This test is so good we sometimes there are other division tests.  
  • The number 5 divides a number only if the last digit is 0 or 5;
  • the number 2 divides a number only if the last digit is even;
  • the number 4 divides a number only if the the number that is last two digits are divisible by 4;
  • the number 8 divides a number only if the number that is the last three digits are divisible by 8;
  • the number 6 divides a number that number is divisible by 3 and 2; see the tests above
This takes care of all of the numbers from 2 to 9 with the exception of 7; this demon 7 became a mystery to me until I become math major and was given the keys to the priesthood.  I am now going to share those with you because I don’t think you will believe me, and if you do believe me, you will just forget about it anyway.  
I dare you to believe me. I double dog dare you.
Okay, take the number you want to divide by and call it d and take the number you want to test and call it T. I’ve lost a bunch of people right there because I’ve used variables. Tough.  When you divide T by d you get a remainder r.  The number T is divisible by d exactly when r is 0. I’ve not said anything now that ought to surprize you.  This process is called reducing modulo d. Forget that bit I said about not wasting imagination on names.
The surprize comes next.  You can reduce modulo d in an amazingly simple way. It is called modular arithmetic.
Let’s go back to our first example.  Is 5543 divisible by 9?  Well, 5643= 5x1000+6x100+4x10+3.  Take every term and factor of this an replace it with its remainder when divided by 9.  It is easy in this case because the 5, the 6, the 4, and the 3 don’t change and the 1000, the 100, the 10, and the 1 are all 1.  So 5x1000+6x100+4x10+3=5x1+6x1+4x1+3x1 which is exactly what we had done before.
Now consider the test for divisibility by 4 which only uses the last two digits of a number.  Why?  Well consider that the third digit will be multiplied by 100, the fourth by 1000, the fifth by 10000, and so on.  Each of these number is evenly divisible by 4 and so leaves a remainder of 0. So 5643= 5x1000+6x100+4x10+3 reduces to 5x0+6x0+4x10+3=43. Here, I am not using the full power of the technique for the sake of demonstrating the classical test.  The 4x10+ 3 would reduce to 4x2+3=11 which would reduce to 3.
You can see how the test for 5 would work out neatly as well because all powers of 10 leave a remainder of 0 when divided by 5.
Let me now go though a more complicated example to show you the full power.  Is 5643 divisible by 7?  I don’t know of any classical test for this. If you do, let me know.  Note that 10 divided by 7 leaves a remainder of 3;  then 100=10x10 will leave the same remainder as 3x3=9 which is 2; so 1000=100x10 will leave the same remainder as 2x3=6, i.e. 6. So 5643=5x1000+6x100+4x10+3 reduces to 5x6+6x2+4x3+3=30+12+12+3 which reduces to 2+5+5+3 which reduces to 5+3 which reduces to 1.  
Therefore 5643 is not divisible by 7, and, indeed, leaves a remainder of 1.   A very short calculation on a calculator will confirm this.
If you have a number like 75867 you can forget about the 7s and reduce it to 5860 which will reduce to 5160 which will reduce to 5x1000+ 100+6x10 which reduces to 5x6+2+ 6x3 which reduces to 2+2+4 which again reduces to 1.  
While I find this to be a very entertaining activity, there does come a point where simply dividing by 7 by hand becomes easier and I suspect that is why this is not taught to mere mortals.