Divisibility by Nine

When I was a GTA at The University of Kansas, I once taught a proof for a number being divisible by nine if and only if the sum of its digits is divisible by nine. I stumbled across the proof the other day and thought I'd go ahead and share it. It's one of my favorites, though I've since learned that it is by no means the simplest. The pdf linked to at the bottom includes multiple proofs related to divisibility rules. It uses modular arithmetic, though, and I've never had an intuitive grasp of that. This proof makes more sense to me, even if it is hard to read. Let me tell you, it was even harder to write in HTML, as I recall - so many subscripts and superscripts!

------------------------------------

If a number is divisible by 9, then the sum of its digits is divisible by 9

A number n with digits [most significant] d_k, d_k-1, ... , d₁, d₀ [least significant] can be rewitten as d_k*10^k + d_k-1*10^k-1 + ... + d₁*10 + d₀

We start by observing that 10^x = 10^x - 1 + 1

Note: 10^x - 1     =     9*10^x-1 + 9*10^x-2 + ... + 9*10² + 9*10 + 9     =     9*(10^x-1 + 10^x-2 + ... + 10² + 10 + 1)

Thus, our number in convoluted form is:
d_k*(9*(10^k-1 + ... + 1) + 1) + d_k-1*(9*(10^k-2 + ... + 1) + 1) + ... + d₁*(9*(1) + 1) + d₀*(1)

If we factor out everything with a 9 in it, we are left with:
9*(d_k(10^k-1 + ... + 1) + d_k-1(10^k-2 + ... + 1) + ... + d₁(1)) + [d_k + d_k-1 + ... + d₂ + d₁ + d₀]

We can see from here that if a number is divisible by 9, then a 9 must be able to be factored out of the part in []'s (a 9 is already factored from the left part. Note that if the digits are divisible by 9, then the number is divisible by 9, too. This follows since we did direct algebraic manipulation of the number without any implications (which are only one way). Thus, a number is divisible by 9 IF AND ONLY IF the sum of its digits is divisible by 9

The same proof except for the last paragraph is used to prove the same about divisibility by 3, since 9 is divisible by 3 on the left side.

------------------------------------

http://www.ms.uky.edu/~lee/as100fa02/divide.pdf [pdf]