Prove that a number is divisible by 3 iff the sum of its digits is divisible by 3

I'm trying to teach myself some number theory. In my textbook, this proof is given:

Example (2.3.1) Show that an integer is divisible by 3 if and only if the sum of its digits is a multiple of 3.

Let $n=a_0a_1\ldots a_k$ be the decimal representation of an integer $n$. Thus $n=a_k+a_{k-1}10+a_{k-2}10^2+\cdots+a_010^k$ where $0\le a_i<10$ The key observation is that $10\equiv1\pmod3$, i.e., $[10]=[1]$. Hence $[10^i]=[10]^i=[1]$, i.e., $10^i\equiv1\pmod 3$. The assertion is an immediate consequence of this congruence.

I don't understand the last statement. Why does it follow from that congruence?

Solution 1:

A simple way to see this (that actually generalizes nicely to Fermat's little theorem):

$$10 - 1 = 9 = 9 \times 1$$ $$100 - 1 = 99 = 9 \times 11$$ $$1000 - 1 = 999 = 9 \times 111$$ In general $$10^n - 1 = 9 \times \underbrace{111...111}_\mbox{$n$ times}.$$ This is just the algebraic identity $$x^n - 1 = (x - 1)(x^{n-1} + x^{n - 2} + ... + x + 1)$$ when $x = 10$. The identity is easy to prove - just multiply it out term by term. All but the first and last terms cancel. Thus any power of $10$ less $1$ is divisible by $9$, and therefore also by $3$.

Now consider a multi-digit natural number, $43617$ for example. $$\begin{align} 43617 &= 4\times 10^4 + 3 \times 10^3 + 6 \times 10^2 + 1 \times 10 + 7 \\ &= 4\times 9999 + 3 \times 999 + 6 \times 99 + 1 \times 9 + (4 + 3 + 6 + 1 + 7) \end{align}$$

Every term on the right other than the sum of the digits is divisible by $3$. So the remainder when dividing the original number by $3$ and the sum of the digits by $3$ must be the same.

Solution 2:

n = $a_0$ + .... + $a_n$ mod (3) means that n and the sum of the digits will be equivalent to the same number modulo 3. If this number is 0 then n and the sum of the digits will both be divisible by 3. If the number isn't 0 (or any other multiple of 3) neither n nor the sum of the digits will be divisible by 3.

Solution 3:

The assertion is an immediate consequence of this congruence.

Since any power of $10$ is congruent to $1$ (mod $3$),

$$n=a_k+a_{k-1}10+a_{k-2}10^2+\cdots+a_010^k\equiv a_k+a_{k-1}+a_{k-2}+\cdots+a_0\pmod3.$$

In other words, the residual of dividing $n$ by $3$ is the same as the residual of dividing the sum of its digits by $3$. In the case of zero residual, we get the sought assertion: $n$ is divisible by $3$ iff the sum of its digits is divisible by $3$.