Proof: Divisible by 9.
I completely forgot about my post from two and a half years ago regarding that little math trick BL brought up regarding numbers divisible by 9. I had discovered that there was a general rule that the difference between two integers will always be divisible by 9 if the two integers are of the same sign, and use the same digits. For example, 4751 and 1574, or 9201 and 291 (i.e. 0291).
I mentioned that I would write down a proof when I had the time, and forgot to.
So I'm going to do it now before I forget. But I apologize in advance for the terrible non-math font.
Any integer can be expressed as a sum of the powers of each digit multiplied by the ten to the power of the digit's position in the number.
For example, 583 = 5 * 100 + 8 * 10 + 3 = 5 * 102 + 8 * 101 + 3 * 100
Let us take an integer N with n digits and express it as a sum of its digits:
N = an * 10n + an-1 * 10n-1 + ... + a1 * 101 + a0 * 100
Where 0 <= ak <= 9 where 0 <= k <= n.
Now take another integer N' that uses the same digits and is the same sign as N.
N' = bn * 10n + bn-1 * 10n-1 + ... + b1 * 101 + b0 * 100
Where 0 <= bk <= 9 where 0 <= k <= n. For example, if N = 583, N' = 385 or 853 but not -358.
We can rewrite N and N' to make most of the terms divisible by 9 by subtracting each digit from each position and grouping it separately:
N = an * (10n - 1 + 1) + an-1 * (10n-1 - 1 + 1) + ... + a1 * (101 - 1 + 1) + a0 * (100 - 1 + 1)
= an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) + an + an-1 + ... + a1 + a0
While:
N' = bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1) + bn + bn-1 + ... + b1 + b0
Using our example above, 583 = 5 * 102 + 8 * 101 + 3 * 100 = 5 * (102 - 1) + 8 * (101 - 1) + 3 * (100 - 1) + 5 + 8 + 3.
Now if we subtract N' from N, we get:
N - N' = an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) + (an + an-1 + ... + a1 + a0) - (bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1)) - (bn + bn-1 + ... + b1 + b0)
But, since N and N' are composed of the same digits, and N and N' are both positive or both negative, then the sum of the digits for both numbers are the same:
an + an-1 + ... + a1 + a0 = bn + bn-1 + ... + b1 + b0
For example 5 + 8 + 3 = 8 + 5 + 3 = 16. So
N - N' = an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) - (bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1))
But now every term is multiplied by (10k - 1) where 0 <= k <= n. An interesting fact is that these terms are all divisible by 9 because (10k - 1) is just a number with k 9s. For example, 102 - 1 = 100 - 1 = 99.
Since each term in the right hand side is divisible by 9 that means that N - N' is also divisible by 9. Thus the difference of two integers of the same sign that share the same digits will always be divisible by 9.
I should post this along with my proofs for the Number of Digits Problem or Divisible Digits Problem but I'm loathe to change a site that I've already promised never to change. I'll figure a way to collect my proofs.
I mentioned that I would write down a proof when I had the time, and forgot to.
So I'm going to do it now before I forget. But I apologize in advance for the terrible non-math font.
Any integer can be expressed as a sum of the powers of each digit multiplied by the ten to the power of the digit's position in the number.
For example, 583 = 5 * 100 + 8 * 10 + 3 = 5 * 102 + 8 * 101 + 3 * 100
Let us take an integer N with n digits and express it as a sum of its digits:
N = an * 10n + an-1 * 10n-1 + ... + a1 * 101 + a0 * 100
Where 0 <= ak <= 9 where 0 <= k <= n.
Now take another integer N' that uses the same digits and is the same sign as N.
N' = bn * 10n + bn-1 * 10n-1 + ... + b1 * 101 + b0 * 100
Where 0 <= bk <= 9 where 0 <= k <= n. For example, if N = 583, N' = 385 or 853 but not -358.
We can rewrite N and N' to make most of the terms divisible by 9 by subtracting each digit from each position and grouping it separately:
N = an * (10n - 1 + 1) + an-1 * (10n-1 - 1 + 1) + ... + a1 * (101 - 1 + 1) + a0 * (100 - 1 + 1)
= an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) + an + an-1 + ... + a1 + a0
While:
N' = bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1) + bn + bn-1 + ... + b1 + b0
Using our example above, 583 = 5 * 102 + 8 * 101 + 3 * 100 = 5 * (102 - 1) + 8 * (101 - 1) + 3 * (100 - 1) + 5 + 8 + 3.
Now if we subtract N' from N, we get:
N - N' = an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) + (an + an-1 + ... + a1 + a0) - (bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1)) - (bn + bn-1 + ... + b1 + b0)
But, since N and N' are composed of the same digits, and N and N' are both positive or both negative, then the sum of the digits for both numbers are the same:
an + an-1 + ... + a1 + a0 = bn + bn-1 + ... + b1 + b0
For example 5 + 8 + 3 = 8 + 5 + 3 = 16. So
N - N' = an * (10n - 1) + an-1 * (10n-1 - 1) + ... + a1 * (101 - 1) + a0 * (100 - 1) - (bn * (10n - 1) + bn-1 * (10n-1 - 1) + ... + b1 * (101 - 1) + b0 * (100 - 1))
But now every term is multiplied by (10k - 1) where 0 <= k <= n. An interesting fact is that these terms are all divisible by 9 because (10k - 1) is just a number with k 9s. For example, 102 - 1 = 100 - 1 = 99.
Since each term in the right hand side is divisible by 9 that means that N - N' is also divisible by 9. Thus the difference of two integers of the same sign that share the same digits will always be divisible by 9.
I should post this along with my proofs for the Number of Digits Problem or Divisible Digits Problem but I'm loathe to change a site that I've already promised never to change. I'll figure a way to collect my proofs.
Comments
Post a Comment