%% -*- compile-command: "latex div3digits && latex div3digits && pdflatex div3digits && o div3digits.pdf" -*-
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\begin{document}
\title{If a number is divisible by 3, then so is the sum of its digits}
\author{Noel Burton-Krahn \\ {\em noel@burton-krahn.com}}
\date{Oct 3, 2016}
\maketitle
\section{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.
\begin{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 lo, $54,321 = 3 \cdot 18,107$.
\end{example}
Is that true for all numbers?
\section{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:
\pagebreak
\begin{lemma}
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$.
\end{lemma}
\begin{proof}
By induction. First the base case where $n=0$: $k_0$ is trivially 0.
\begin{align*}
(x+1)^0 & = 1 \\
& = x \cdot 0 + 1
\end{align*}
Now, the inductive step. Assuming $n$, prove $n+1$:
\begin{flalign*}
(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{flalign*}
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$.
\end{proof}
\begin{lemma}
if $D = p k + q$, then $D$ is divisible by $p$ if and only if $q$ is divisible by $p$.
\end{lemma}
\begin{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$.
\end{proof}
Now we can get back to the main theorem.
\pagebreak
\begin{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.
\end{theorem}
\begin{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.
\end{proof}
\section{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$
\end{document}