0
$\begingroup$

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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).$$

$\endgroup$
1
$\begingroup$

Yes your proof is correct and works for both $3$ and $9$

Please polish your proof because you have missed a parenthesis somewhere in your proof.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.