# LUCAS WILLEMS

A 23 year-old student passionate about maths and programming

# Divisibility by 3

## Article

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.

Summary

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

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

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