Proof that if a number is divisible 9, so are the sum of its digits

There is a well-known “rule” in maths that if a number is divisible by 9, then the sum of all its digits are also divisble by 9. Of course, 9 itself is the trivial example. Let’s work up in multiples: 18, 27, 36, 45. Each of these conforms to the “rule.”

Let’s take a bigger number. Let’s multiply 9 by 985,939 (I generated this number randomly using Excel). What we get is 8,873,451. Well 8+8+7+3+4+5+1=36 which is divisible by 9.

So what I want to do here is demonstrate a proof that this is true.

Let x be an integer, expressed in the following expansion of powers of 10:

N = a0100 + a1101 + … + an10n

where all ai are integers in the set {0,1,2,3,4,5,6,7,8,9} and where n is finite.

If 9|N then our proposition then becomes 9|∑ai.

If 9|N then it naturally follows that N = 9Y for some integer Y. Let’s express Y similarly as for N.

Y = b0100 + b1101 + … + bn10m

We can then get to our equation which falls naturally out of this that:

(*) a0100 + a1101 + … + an10n = 9b0100 + 9b1101 + … + 9bn10m

I have put a star by it because we will need to come back to it later.

At this point, it’s helpful to recall the nature of modular arithmetic. If you’ve not come across it before, don’t worry it’s quite simple, as well as being powerful and fun, which is what makes maths great!

In modular arithmetic, you limit the number of integers you can use. Once you run out, you go round and start again. Let’s say for example, that we wanted to work in modulo 10. This would mean that we could not have any numbers that are 10 or greater.

What we do is we would keep taking off 10 until we got to a positive integer that was less than 10. So for example, if we wanted to know what is 23 (mod 10)? Well, 23 is clearly greater than 10. So we take 10 off. This gives us 13, which is still greater than 10. Take off another 10 and we can see that 23≡3(mod 10). This is read as ‘twenty-three is congruent to three, modulo ten.’

Working in mod 10 is fairly trivial. However, what is 10 (mod 10)? Well, that’s zero. If you’re not sure why, then re-read the last sentence of the previous-but-one paragraph. This has a handy consequence that we are working in mod n, then anything which is 0 (mod n) means that it is divisible by n.

We can also use normal rules of arithmetic, except for division, if we are dealing only with integers. So, we could ask what is 3 x 4 (mod 8)? Well, we know that 3 x 4 = 12, so the question becomes what is 12 (mod 8)? This should be clear that this is 4.

Let’s take another example (you will see why in a bit). What is 9 x 9 (mod 8)? Well, 9 (mod 8) is 1. So the problem is identical to asking what is 1 x 1 (mod 8).

This is clearly 1. We could have calculated 9 x 9 = 81 and kept taking 8 off until we got back to 1.

Now, what happens if we take (*) and take both sides modulo 9?

Well, you can break each part down and say the following:

Well,

(1) 10k≡1 (mod 9) for all integer values of k.
(2) 9bj≡0 (mod 9) for all integer values of j.

By (1) we can see that the left hand side of (*) becomes a0 + a1 + … + an.

By (2) we can see that the right hand side of (*) becomes zero.

Hence ∑ai≡0 (mod 9) and therefore our proposition that 9|∑ai is proved.

Q.E.D.

Advertisements

Comments are closed.