Preamble

This is a toy proof of a math trick I learned in elementary school. It's really Just an excuse to play with $\LaTeX$.

This document is also available as PDF and $\LaTeX$ source.

Introduction

There was a trick we learned in elementary school: if the sum of the digits of a number is divisible by 3, then the number itself is divisble by 3.

Example: Is $54,321$ divisible by $3$? The sum of digits $5 + 4 + 3 + 2 + 1 = 15$, which is divisible by $3$, so $54,321$ should be divisible by $3$ according to this rule, and yes, $54,321 = 3 \cdot 18,107$.

Is that true for all numbers?

Proving it

We write numbers as strings of decimal digits like so:

$$ \begin{align*} 54,321 & = 5 \cdot 10,000 + 4 \cdot 1,000 + 3 \cdot 100 + 2 \cdot 10 + 1 \\ & = 5 \cdot 10^4 + 4 \cdot 10^3 + 3 \cdot 10^2 + 2 \cdot 10^1 + 1 \cdot 10^0 \end{align*} $$

More precisely, we write an integer $D$ as a string of decimal digits: $d_{n-1},{\ldots},d_1,d_0$, which represents the equation:

$$ \begin{align*} D & = d_{n-1} 10^{n-1} + \cdots + d_1 10^1 + d_0 10^0 \\ & = \sum_{i=0}^{n-1} d_i 10^i \end{align*} $$

Given that definition of the digits of a number, we can prove the theorem. First, a couple of mini-theorems:

Lemma 1: For all integer polynomials, $(x+1)^n = x k_n + 1$ for some integer $k_n$. In other words, $(x+1)^n - 1$ is divisible by $x$.

Proof: By induction. First the base case where $n=0$:

$$ \begin{align*} (x+1)^0 & = 1 \\ & = x \cdot 0 + 1 \end{align*} $$

So for the base base, $k_0 = 0$.

Now, the inductive step. Assuming $n$, prove $n+1$:

$$ \begin{align*} (x+1)^{n+1} & = (x + 1)(x + 1)^n \\ & = (x + 1)(x k_n + 1) && \text{assuming $n$: $(x+1)^n = x k_n + 1$} \\ & = x x k_n + x + x k_n + 1 \\ & = x(x k_n + k_n + 1) + 1 \\ & = x(k_{n+1}) + 1 && \text{where $k_{n+1} = x k_n + k_n + 1$} \end{align*} $$

We've proven the $n+1$ case: $(x+1)^{n+1} = x k_{n+1} + 1$, and by induction this is be true for all $n \ge 0$. $\square$

Lemma 2: If $D = p k + q$, then $D$ is divisible by $p$ if and only if $q$ is divisible by $p$.

Proof: Assume $q$ is divisible by $p$. Then, $q = p j$ for some integer $j$, and

$$ \begin{align*} D & = p k + q \\ & = p k + p j \\ & = p (k + j) \end{align*} $$

thus $D$ is divisible by $p$.

Now, assume $q$ is {\bf not} divisible by $p$. Then, $q = p j + r$ for some $0 < r < p$, and

$$ \begin{align*} D & = p k + q \\ & = p k + p j + r \\ & = p (k + j) + r \end{align*} $$

and since $0 < r < p$, $D$ is {\bf not} divisible by $p$.

Thus $D = p k + q$ is divisible by $p$ if and only if $q$ is divisible by $p$. $\square$

Now we can get back to the main theorem.

Theorem: If an integer $D$ is written as a string of digits $d_{n-1},\ldots,d_1,d_0$ where $D = \sum_{i=0}^{n-1} d_i 10^i$, then $D$ is divisible by 3 if and only if the sum of its digits $S = \sum_{i=0}^{n-1} d_i$ is divisible by 3.

Proof: The proof uses the simple fact that $10 = (9 + 1)$:

$$ \begin{align*} D & = \sum_{i=0}^{n-1} d_i 10^i \\ & = \sum_{i=0}^{n-1} d_i (9+1)^i \\ & = \sum_{i=0}^{n-1} d_i (9k_i+1) && \text{by Lemma 1}\\ & = 9\sum_{i=0}^{n-1} d_i k_i + \sum_{i=0}^{n-1} d_i\\ & = 9k + S && \text{where $S$ is the sum of the digits of $D$} \end{align*} $$

So $D = 9k + S$, and by Lemma 2, $D$ is divisible by 9 if and only if the sum of its digits, $S = \sum_{i=0}^{n-1} d_i$ is also divisible by 9. That's an interesting result, but we were trying to prove that statement for 3. However, since $9 = 3 \cdot 3$:

$$ \begin{align*} D & = 9k + S \\ & = 3 \cdot 3 k + S \\ & = 3 j + S \end{align*} $$

Lemma 2 works again to prove that $D$ is divisible by 3 if and only if the sum of its digits, $S = \sum_{i=0}^{n-1} d_i$ is also divisible by 3. $\square$

Epilogue

This proof used the fact that we write integers in base 10, and $10 = (9+1)$, and thus if the sum of a number's digits in base 10 is divisible by 9 or 3, then so is the number itself. This works for other bases too. For example, if the number's digits are in base 8, this rule will work for all divisors of $8 - 1 = 7$. For example, $5432_8 = 2842_{10} = 7 \cdot 406_{10}$, and $5+4+3+2 = 14_{10}\checkmark$

If a number is divisible by 3, then so is the sum of its digits

Preamble

Introduction

Proving it

Epilogue

Comments