Prove that if the sum of digits of a number is divisible by 3, so is the number itself.

Here is the proof of the converse:

Iff a number $n$ is divisible by $3$, then the sum of its digits is also divisible by $3$.

Proof:

We know $n \mod 3 = 0$. By the basis representation theorem, $n$ can be re-written as $n_k10^k + n_{k-1}10^{k-1} + \cdots + 10n_1 + n_0 \equiv 0 \mod 3$. By the modular arithmetic addition rule, we can take $n_k10^k \mod 3 + n_{k-1}10^{k-1} \mod 3 + \cdots + 10n_1 \mod 3 + n_0 \mod 3$. But then we just get $n_k + n_{k-1} + \cdots + n_1 + n_0$, since $10 \mod 3 \equiv 1$.

Now suppose that the sum of the digits was divisible by 3. How can I prove that the representation in base $10$ is divisible by $3$?

Solution 1:

The key point which you seem to have noted is that $10\equiv 1\pmod{3}$. This means that a number is congruent to the sum of its digits mod 3 because $10^k\equiv 1\pmod{3}$, which you also seem to have noted. Thus $n$ is divisible by $3$ (congruent to $0$ mod 3) if and only if the sum of its digits is. The same is true for other remainders modulo 3; a number has a remainder of $1$ when divided by $3$ if and only if the sum of its digits does, etc.

Your observation that $10^k\equiv 1\pmod{3}$ is the reason why it has been commented that you have already proved the result.

Solution 2:

I hope this will suffice: $$ n = (d_{m-1}\cdots d_0)_{10} = \sum_{k=0}^{m-1} d_k 10^k = \sum_{k=0}^{m-1} d_k (10^k - 1) + d_k = \sum_{k=0}^{m-1} d_k (10^k - 1) + S(n) $$ with $S(n)$ being the digit sum in base $10$ and $$ 10^k - 1 = 9 \frac{10^{k} - 1}{10-1} = 9 \sum_{i=0}^{k-1} 10^i = \sum_{i=0}^{k-1} 9 \, 10^i = (\underbrace{9\cdots 9}_{k \times})_{10} $$ is divisible by $3$, it depends on the divisibility of $S(n)$.

The same statement should hold for division by $9$.