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

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:

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\):

So for the base base, \(k_0 = 0\).

Now, the inductive step. Assuming \(n\), prove \(n+1\):

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

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

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)\):

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\):

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

## Comments

comments powered by Disqus