Casting Out Nines - Proof

Date: 08/30/2002 at 10:51:06
From: Tosha Burchette
Subject: Casting out nines

Show that if the order of the digits of a natural number is permutated 
to form a new number, the difference between the old number and the 
new number is divisible by 9.

I know that this works, but I am having difficulty proving why.

Date: 08/30/2002 at 12:30:39
From: Doctor Peterson
Subject: Re: Casting out nines

Hi, Tosha.

Any permutation can be obtained by a sequence of interchanges in 
which we swap one pair of digits. So it is enough to show that the 
difference is divisible by 9 if we swap any two digits. (You can fill 
in the details.)

Suppose the digits of the number are a_n ... a_1 a_0, so that the 
value of the number is

    a_n*10^n + ... + a_i*10^i + ... + a_j*10^j + ... + a_1*10 + a_0

Then if we swap digits a_i and a_j (I'll assume i>j), the new value 
will be

    a_n*10^n + ... + a_j*10^i + ... + a_i*10^j + ... + a_1*10 + a_0

The difference is then

    (a_i*10^i + a_j*10^j) - (a_j*10^i + a_i*10^j)

      = (a_i - a_j)*10^i - (a_i - a_j)*10^j

      = (a_i - a_j)(10^i - 10^j)

      = (a_i - a_j)(10^(i-j) - 1)10^j

So we can prove our goal if we can show that

    10^n - 1 = 9k

for some k, for any positive integer n. (Think about writing such a 
number out, and you will immediately see that it is true; but we 
still need to prove it.)

Now consider the polynomial

    x^n - 1

Since it is zero when x=1, it has (x-1) as a factor. For example, 
x^2 - 1 = (x+1)(x-1).

Can you use this fact to prove what we want?

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/