[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 10⁰ = 1,  10¹ = 10,  10² = 100,  10³ = 1 000,  10⁴ = 10 000,  10⁵ = 100 000,  etc  all leave a remainder of  1  when divided by  9.   Thus in our example,

     685932 = 6´10⁵ + 8´10⁴ + 5´10³ + 9´10² + 3´10¹ + 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 = d_k ´10⁴ + ... + d₃´10³ + d₂´10² + d₁´10 + d₀.    

Since  10^k º 1 (mod 9)  for all integers  k > 0,  we have

                 n º d_k´1 + ... + d₃´1 + d₂´1 + d₁´1 + d₀

                 n º    d_k  + ... +   d₃   +    d₂  +   d₁    + d₀     (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

[OlymPri20151105NTC9] An x to Find by Casting Out Nine

Question

In class, John was thinking of a 6-digit number, A.  He added up all the digits and got the result, B.  Then, he subtracted  B  from  A, which gave a result, another 6-digit number, whose digits consist of 0, 2, 4, 6, 8 and  x.  Find a possible answer for  x.

Introduction

     This problem looks mind-boggling.  There are so many possible 6-digit numbers and there seems to be no clue as to how to even begin.  This problem hinges on a forgotten fact that many people used to learn when electronic calculators were not so prevalent.

Old Wine Most Fine

     It is a fact that any number is equivalent to its sum ofdigits in the sense that they both have the same remainder when divided by 9.  (see this article)  This is the principle behind the method of “casting out nines”, used in the past for checking arithmetical calculations.  Mathematics is never out-dated.  In fact, some of the old forgotten theory may sometimes turn out surprisingly useful.  If two numbers  x  and  y  have the same remaider when divided by 9,  we can write  x  º  y  (mod 9)  but in this article, I shall just write  x º y.  If   x º 0,  it just means that  x  has no remainder when divided by  9  i.e.    x  is a multiple of  9.

Solution

     Since                             A º B      where  B = sum_of_digits(A),

                                    A – B º 0

             sum_of_digits(A – B) º 0

           0 + 2 + 4 + 6 + 8 + x  º 0

                                  20 + x  º 0  [ 20 + x  is a multiple of  9]

                                     \  x  º 7  [x  is a digit & the next higher multiple of  9  is 27]

Remark

     One possible value of  A  is  864738.  Then  A – B = 864738 – 36 = 864702

Heuristics Used

H04. Look for pattern(s)

H05. Work backwards

H09. Restate the problem in another way

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* Primary School Mathematics Olympiad

* syllabuses that involve congruences and Number Theory

* anybody who is interested