In little people school I/we learned that if the sum of a number’s digits are evenly divisible by three, then the number is as well.
This is very cool, and for most people its good enough.
Not for me. I demand proof!
I went digging around the internet, and found squat. So I started in on it, using induction:
Prove it is true for n(1). The first number whose sum is divisible by 3 is 3, which is divisible by 3.
Assume it is true for n. Prove it is true for n+1.
Let X be a number that is evenly divisible by 3. Assume that sum of the digits of X : k+m+n are also evenly divisible by 3. The next number in the series is X+3, whose digits are one of:
k=k, m=m, n=n+3, for n<7
k=k, m=m+1, n=n-7 for n>=7, m!=9
k=k+1, m=m-9, n=n-7 for n>=7, m=9
If k+m+n is divisible by three, then:
- (k+m+n)+3 is divisible by three, since k+m+n is divisible by 3 and 3 is divisible by 3.
- k+m+1+n-7 == k+m+n-6 is divisible by three, since k+m+n is divisible by 3 and -6 is divisible by 3.
- k+1+m-9+n-7 == k+m+n -15 is divisible by three, since k+m+n is divisible by 3 and -15 is divisible by 3.
- For further carryover, we are adding extra -9s, which are divisible by 3, and finally a +1, which makes the -7 a -6, divisible by 3.
This is great, and I was very proud of myself, but I don’t think it proves what I want it to - I believe I have proved that “if a number is divisible by 3, the sum of its digits is as well” which seems to be a far cry from the converse, what I originally wanted to prove.
Does anyone have an elegant proof for the original statement? Or at least a more elegant proof for the converse, and/or some reasoning why this also means the converse must be true?
Also, I’m interested in proof for the divide-by-two rule (if the one’s digit is evenly divisible by 2, the number is).