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^{0} = 1,
10^{1} = 10, 10^{2}
= 100, 10^{3} = 1 000, 10^{4} = 10 000, 10^{5} = 100 000, etc all leave a remainder of 1 when
divided by 9. Thus in
our example,
685932 = 6´10^{5} + 8´10^{4} + 5´10^{3} + 9´10^{2} + 3´10^{1} + 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 [d_{k}...d_{3}d_{2}d_{1}d_{0}]
n º d_{k}
+ ... + d_{3} + d_{2} + d_{1} + d_{0} (mod 9)

n = d_{k} ´10^{4} + ... + d_{3}´10^{3} + d_{2}´10^{2} + d_{1}´10 + d_{0}.
Since 10^{k} º 1 (mod 9) for
all integers k > 0, we have
n º d_{k}´1 + ... + d_{3}´1 + d_{2}´1 + d_{1}´1 + d_{0}
n º d_{k} + ... +
d_{3} + d_{2} + d_{1}
+ d_{0}
(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