Summation Proof Dealing With 3s Multiples So the problem is as follows:
Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because $1+1+2+3+4+5+6+7=24$, and in fact, $11234567$ is $3744856 * 3$. Use $10^n \equiv 1 \pmod3$ if necessary.
I am having a lot of problems with this question seeing as it is a rather difficult problem. Could someone please help me solve this? Thank you!
 A: In decimal basis, your number $n$ can be written as $n = d_0 + d_1 10 + \cdots + d_k 10^k \equiv d_0 + d_1 + \cdots + d_k \pmod3$.
I used $10^m \equiv 1 \pmod 3$ for all natural $m$.
Moreover, it follows that the sum of the digits of $n$ is the remainder of $n$ divided by 3.
A: Maybe you could first prove that the sum of the digits subtracted from the number is a multiple of 9.
For example, a 4 digit decimal number such as $1234=1\times1000+2\times100+3\times10+4$
But $1000=999+1$, $100=99+1$ and $10=9+1$.
So $1234=1\times\left(999+1\right)+2\times\left(99+1\right)+3\times\left(9+1\right)+4$.
And finally, $1234=1\times999+2\times99+3\times9+\left(1+2+3+4\right)$, or $1234-\left(1+2+3+4\right)=999+2\times99+3\times9$.
I'm sure you can come up with the rest of the proof.  All you have to do is show that every power of $10$ is $1$ more than a multiple of $9$.  And remember, $9$ is a power of $3$ so the difference between the digital sum and the number is also a multiple of 3.
Okay - here is a proof that any power of 10 is 1 more than a multiple of 9, by induction:
$10^0=1=0\times9+1$
$10^1=10=9\times1+1$
$10^2=100=9\times11+1$
Clearly our hypothesis is true for $n=0,1,2$.
Assume it is true for some arbitrary $n$, so $10^n$ is $1$ more than a multiple of $9$.
More formally: $10^n=9\times m+1$, for some integer $m$.
Then $10^{n+1}=10^n\times10\\
=\left(9\times m + 1\right)\times10\\
=9\times10\times m+10\\
=9\times10\times m+9+1\\
=9\times\left(10\times m+1\right)+1$
We are given $m$ is an integer, so $10\times m$ is an integer and so is $10\times m+1$ (multiplication and addition are closed on the integers).  Then $9\times\left(10\times m+1\right)$ is $9$ times an integer or in other words, a multiple of $9$.
So clearly, when $10^n$ is $1$ more than a multiple of $9$ so is $10^{n+1}$.
