Fun Math proof to try

[Sela]

And unlike several of the proofs I've seen posted, it's actually an easy enough problem to understand. I've come up with something which I feel is 'proof'; but it's not very formal and I'm not even 100% sure my logic was right. Still, figured I'd post it here to see who got a kick out of it.

PROVE: For any number 'x' such that 'x' is a multiple of 9, the sum of the digits of 'x' is also a multiple of 9.

For example, 9*43 = 387; and since 387 is a multiple of nine, 3+8+7 = 18 must also be a multiple of nine (18/9 = 2).


I'll give my answer after a few posts here or whenever its appropriate.

[Molyneux]

That's an interesting question...after a few minutes of racking my brain, I really can't say that I can see how to try to prove it. I have heard that it's true (and similarly true for 3) before, and have never come across a counterexample, but I can't be sure of the reason.

[Kuroneko]

It's a special case of the property that the remainder of a number after division by 9 is the same as the remainder one gets by using the sum of the digits instead. This used to be a well-known fact on which an arithmetic-checking technique called "casting out the nines" was based on. I don't think it's taught any longer in the US public school curriculum--I doubt many remember such divisibility rules without the constant reinforcement of checking their arithmetic. Spoiler

It's equivalent to the statement 10n = 1 (mod 9), which is easy, since 10n = 9[1+10+...+10n-1]+1. Thus the sum of the values of the digits is equivalent to the sum of the digits.

The same thing applies to 3, as well as a slight variation for 11:
-- The remainder of a number after a division by 11 is the same as that of the alternating sum of its digits, e.g., 146/11 = 13+3/11 while (6-4+1)/11 = 3/11. Flip negatives if need be.

[General Soontir Fel]

A decimal representation of any number is sum(from i = 0 to Infinity) [a_i *10^i].
The sum of the digits of that number is sum(from i = 0 to Infinity) a_i.

Subtracting the sum of the digits from the number, you get sum(from i = 0 to Infinity)[a^i * (10^i - 1)].

For any non-negative i, 10^i - 1 is a multiple of 9 (10^0 = 1, so in that case, the multiple is 0).

Thus, the above is true for any number: the difference between the number and the sum of its digits is a multiple of 9.

But that means that if the number itself is a multiple of 9, so is the sum of its digits. You can't add two numbers, one a multiple of 9, and one not, and get a multiple of 9 in the sum.

[Bottlestein]

When you say "Number" , I assume you mean "Integer in Base 10 representation"?

Anyways: (Notation: "</=" denotes "less than or equal to", analogous notation for "greater than or equal to"; How the hell do you import LaTeX into here? )

Let x denote an integer such that x = Sum0</=k</=N[(10k)xk] (i.e. in Base 10 representation)
Assume further that x is divisible by 9

We claim that: y=Sum0</=k,</=N[xk] is divisible by 9

Proof:
x = Sum0</=k</=N[(10k)xk]
= Sum1</=k</=N[9*(10k-1)xk + (10k-1)xk] + x0
= Sum1</=k</=N[9*(10k-1)xk] + Sum2</=k</=N[9*(10k-2)xk + (10k-2)xk] + x0
It is clear we can continue this process (!0 ^a = 9* (10 ^ (a-1)) + 10 ^ (a-1)), to get:
=Sum1</=k</=N[9*(10k-1)xk] + Sum2</=k</=N[9*(10k-2)xk] + Sum3</=k</=N[9*(10k-3)xk] + ... + SumN-1</=k</=N[9*(10k-(N-1))xk] + 9* (10N)xN + {xN + xN-1 + xN-2 + ... + x0}

Now note every term but the quantity in "{...}" is divisible by 9, since they can be expressed as "9 * integer"
Therefore, by the definition of divisibility on the integers, x is divisible by 9 implies the quantity in "{...}" is divisible by 9.

[Bottlestein]

Okay - Kuroneko sketched out the most important part of the proof while I was typing al that up...

[Sela]

The really sad part is that I remember some of these terms from discrete mathematics back in undergrad . . . and have a really hard time following the rest.

My way of proving it kinda relied on a hodge-podge of mathematical induction and showing all possible cases for the end-digit; but it's needlessly messy compared to the more elegant proofs you guys have outlined. Fun stuff .

[Sela]

So I finally fully got the implications of your "assume base 10" comment .

A more general statement which is still true, then, and can be proved with only a slight variation on the proofs already outlined:

For any Base X system (where X>= 1(unary) ie: Base 10 for decimal, base 16 for hex, etc.), the sum of the digits of any multiple of X-1 is equal to a multiple of X-1.

[Kuroneko]

Why not just say that a natural number and the sum of its digits in base X are equivalent modulo X-1? It's a more powerful statement making the assumption that the number is a multiple of (X-1) unnecessary, and it makes divisibility testing possible.
Your statement is
[P1] If a natural number is a multiple of (X-1), then the sum of its digits in base X is as well,
which is weaker than
[P2] A natural number is a multiple of (X-1) if, and only if, the sum of its digits in base X is multiple of (X-1),
which is weaker than
[P3] A natural number and the sum of its digits in base X have the same remainders after division by X-1 (i.e., they're equivalent modulo X-1).
At least [P2] is required for testing divisibility, and at least [P3] is required for a "casting out the (X-1)'s" method for arithmetic-checking.