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

- Noel Burton-Krahn