Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search