Question

For the idle mind: Prove that a number whose digits sum to three or nine is divisible by 3 or 9, respectively.

Answer 1

Not a proof, but here's my thought process.
Every (positive) number can be written in the following way:
\[\large\sum_{n=1}^k10^{n-1}x_n,\]
where x_n is the digit in the 10ⁿ-th place, and k is the number of digits.

So as an example (which I picked specifically to be divisible by 3), take 3840:
\[\begin{align*}3843&=10^0(3)+10^1(8)+10^2(8)+10^3(3)\\
&=(9+1)^0(3)+(9+1)^1(8)+(9+1)^2(4)+(9+1)^3(3)\\
&=(27+3)+(72+8)+(81+18+1)(4)+(729+243+27+1)(3)\\
&=(27+3)+(72+8)+(324+72+4)+(2187+729+81+3)\\
&=(27+3+72+324+72+2187+729+81+3)+(8+4)\\
&\;\;\;\;\;\;\;\;\small\text{(all immediate multiplies of 3 are grouped together)}\\
&=27+3+72+324+72+2187+729+81+3+12\\
&=3(9+1+24+108+24+729+27+1+4)\end{align*}\]
Thus 3 divides 3843. Is there anything I can say about any integer in general using this kind of decomposition?

Answer 2

Here's how I know it. As you stated, any number can be written\[a_n\cdot10^n+a_{n-1}\cdot10^{n-1}+\cdots+a_2\cdot10^2+a_1\cdot10^1+a_0\cdot10^0\]let's just use a 3-digit number for illustrative purposes:\[a\cdot10^2+b\cdot10^1+c\cdot10^0\]this can be broken up as\[99a+9b+a+b+c\]\[9(11a+b)+a+b+c\]this is clearly divisible by 3 only if a+b+c is divisible by 3, and similarly with 9.

Answer 3

That's correct.