Lucas Willems

LUCAS WILLEMS

A 21 year-old student passionate about maths and programming

Français

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

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

Search

Here are the searches for this page :

Comments

What do you think ? Give me your opinion (positive or negative) in order to improve it.