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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum