# proof that the sum of digits of natural number are divisible by 3 iff the number is [duplicate]

Im trying to prove that every natural number is divisble by three if and only if the sum of its digits are divisible by three.

First i proved by induction that $$10^n-1$$ is divisible by 9 (and therefore 3) so i could use this in the next step, would this be valid...

ANy natural number can be given a decimal representation

Let $$s\in N$$

Let $$k_0,k_1...k_n\in$${$${0,...10}$$}

$$S=k_0 +10k_1+100k_2+...k_n10^n$$

$$= 9k_1 + 99k_2 + ... + k_n(10^n-1) + (k_0+k_1+...k_n)$$

All terms are divisible by 3 but the sum of the digits in S. Therefore Dividing S by 3 will leave the same remainder as dividing the digits bys 3.

Is this a valid proof of the claim? Thank you for your time

## marked as duplicate by Bill Dubuque, Lord Shark the Unknown, max_zorn, ancientmathematician, vrugtehagelNov 19 '18 at 15:02

It's fine, except that after the last $$=$$ sign you should have written$$9k_1+99k_2+\cdots+\overbrace{99\ldots9}^{n\text{ times}}k_n+(k_0+k_1+\cdots+k_n).$$
Yes your proof is correct and works for both $$3$$ and $$9$$
Yes, don't forget your braces in $$(10^n-1)$$ in the last line of your equation.
In modulo arithmetic, we have $$10^n \equiv (3^2+1)\equiv 1\pmod{3}$$
Hence $$\sum_{i=0}^n a_i\cdot 10^i\equiv \sum_{i=0}^n a_i\cdot 1^i\equiv \sum_{i=0}^n a_i \pmod{3}$$