We will prove the following critereon of divisibility by 3 :

A number is divisible by 3 if and only if the sum of its digits is divisible by 3.

Proof

Before starting the proof, I'm going to show you the idea through an example. Let's take 2456 that we can write as follow :

$$\begin{align} 1456 &= 2 \times 1000 + 4 \times 100 + 5 \times 10 + 6 = 2 \times (999 + 1) + 4 \times (99 + 1) + 5 \times (9 + 1) + 6 \\ &= (2 \times 999 + 4 \times 99 + 5 \times 9) + (2 + 4 + 5 + 6) \end{align}$$

So, as we know \(2 \times 999 + 4 \times 99 + 5 \times 9\) is divisible by 3, the divisibility of 2456 only depends on that of \(2+4+5+6\).

Let's write this reasoning more strictly.

First, we need to prove that numbers with only 9 (99, 999, 9999...) are divisible by 3. To do it, we just have to write these numbers like this :

$$\sum_{k = 0}^{n} 9 \times 10^k$$

which leads us to :

$$\sum_{k = 0}^{n} 9 \times 10^k = \sum_{k = 0}^{n} 3 \times 3 \times 10^k = 3 (\sum_{k = 0}^{n} 3 \times 10^k)$$

​and which allows us to easily see that these numbers are divisible by 3.

Now, let's prove what is interesting us. Let's let \(a\) a \(n\)-digit integer that we can write as follow :

$$a = \sum_{k=0}^{n} a_k \times 10^k \qquad (a_1, ..., a_n) \in [[0, 9]]^n$$

which leads us to :

$$a = \sum_{k=0}^{n} a_k \times 10^k = \sum_{k=0}^{n} a_k \times (10^k - 1 + 1) = \sum_{k=0}^{n} a_k \times (10^k - 1) + \sum_{k=0}^{n} a_k$$

​However, all numbers of the kind \(10^k - 1\) only contain 9, so are divisible by 3. Conclusion :

$$\sum_{k=0}^{n} a_k \times 10^k \equiv \sum_{k=0}^{n} a_k [3]$$