Monday, November 16, 2015

[NumTh Expository] The Principle Behind Casting Out Nines

Introduction
Think of a number ... say 685932.  Divide by  9  and take the remainder.
     685932 ¸ 9      = 76214 r 6 
Add up the digits,  divide by  9  and take the remainder.
     6+8+5+9+3+2 = 33 ¸ 9 = 3 r 6 

What do you notice?  Try this with any other positive whole number.

Discussion
     Did you see that a number and its sum of digits always have the same remainder when divided by  9?  This is the principle behind the method of “casting out nines”, used in the past for checking arithmetical calculations.  Why does this work?  Where is its magic?
     The decimal number system that we use today is based on the number  10, which is just  1  larger than  9.  Observe that  9, 99, 999, 9 999, 99 999, ... etc are all divisible by  9.  Hence, the powers of 10, namely 100 = 1,  101 = 10,  102 = 100,  103 = 1 000,  104 = 10 000,  105 = 100 000,  etc  all leave a remainder of  1  when divided by  9.   Thus in our example,
     685932 = 6´105 + 8´104 + 5´103 + 9´102 + 3´101 + 2´1
                  = 6´(99999+1) + 8´(9999+1) + 5´(999+1) + 9´(99+1) + 3´(9+1) + 2´1
                  = 6´99999+8´99995´999+9´993´9 + 6´1+8´1+5´1+9´1+3´1+2´1
                  = 9 ´ something + 6+8+5+9+3+2
As you can see, all the “´1” allow us to separate out the digits, and then the stuff with 9, 99, 999 etc can be lumped together as 9 ´ some whole number, but we do not need to care too much about this multiple of 9 as it would not make any difference to the remainder.  It is now obvious that  685932 and 6+8+5+9+3+2=33 will have the same number when divided by 9.
     Let us generalise the argument.   If two numbers  x  and  y  have the same remaider when divided by 9,  we say that  x  and  y  are congruent modulo 9, and we write     x  º  y  (mod 9).  Congruence is an equivalence relation and “º” behaves in many ways similar to “=”.

Theorem
For an arbitrary number  n   with digits  [dk...d3d2d1d0]
                                        n º dk + ... + d3 + d2 + d1 + d0   (mod 9)
                 n = dk ´104 + ... + d3´103 + d2´102 + d1´10 + d0.    
Since  10k º 1 (mod 9)  for all integers  k > 0,  we have
                 n º dk´1 + ... + d3´1 + d2´1 + d1´1 + d0
                 n º    dk  + ... +   d3   +    d2  +   d1    + d0     (mod 9).   © (Q.E.D.)

As an example of application of this principle, please refer read thisarticle.

Suitable Levels
Primary School Mathematics Olympiad
* syllabuses that involve congruences and Number Theory
* anybody who is interested





No comments:

Post a Comment

Note: Only a member of this blog may post a comment.