| |
Date: Tue, 16 Feb 1999 19:20:16 -0600 (CST)
Name: Razzi
Who is asking: Student
Level: Secondary
Question:
Hello,
I've been having a hard time trying to solve the following problem and I was wondering if you could help me.
For any positive integer a let S(a) be the sum of its digits. Prove that a is divisible by 9 if and only if there exist a positive integer b such that S(a)=S(b)=S(a+b).
Hi
We are going to assume that you know that an integer is divisible by 9 if and only if the sum of its digits is divisible by 9, and that you know modular arithmetic or casting out nines.
First assume that a is divisible by 9, then the sum of its digits is a multiple of 9, say 9k. Write the number a and construct b as follows. Below each 0 digit in a write 0 and below each 9 digit in a write 9. Now complete the integer b with zeros and nines so that b has no more digits then a and 9k of the digits of b are nines. For example
2309940 <-- a
909900 <-- b
Now add a and b ignoring the carries to get c. Continuing with the example
2309940 <-- a
909900 <-- b
_______
2208840 <-- c
There are three facts to notice about c.
- The digit 9 does not appear in c.
- If B has a 9 in some position then the digit of c in that position is one less than the digit of a in that position.
- In every other position the digits of a and c are the same.
Thus the sum of the digits of c is k less than the sum of the digits of a. If you now perform the k carries to complete the addition of a and b, each increases a digit of c by one and thus the sum of the digits of a + b is 9k.
For the converse suppose that S(a)=S(b)=S(a+b). We are going to use modular arithmetic but you could also use the procedure of casting out nines. The crutial fact here is that S(a+b) is congruent to S(a)+S(b) modulo 9. Thus, working modulo 9, S(a) is congruent to S(a)+S(b) which is S(a)+S(a)=2S(a). Thus S(a) is congruent to 2S(a) and hence S(a) is congruent to 0 modulo 9. Therefore a is divisible by 9.
Cheers,
Chris and Harley
|
|