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

Preamble

This is a toy proof of a math trick I learned in elementary school. It’s really Just an excuse to play with $\text{LATEX}$.

This document is also available as PDF and $\text{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 divisible by 3.

Example: Is $54,321$ divisible by $3$? The sum of digits is $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{array}{rl}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{array}$$

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

$$\begin{array}{rl}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{array}$$

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{array}{rl}(x+1{)}^0& =1\\ & =x\cdot 0+1\end{array}$$

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

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

$$\begin{array}{rlrl}(x+1{)}^{n+1}& =(x+1)(x+1{)}^n& & \\ & =(x+1)(x{k}_n+1)& & \text{assuming n: (x+1)n=xkn+1}\\ & =xx{k}_n+x+x{k}_n+1& & \\ & =x(x{k}_n+k_n+1)+1& & \\ & =x(k_{n+1})+1& & \text{where kn+1=xkn+kn+1}\end{array}$$

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=pk+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=pj$ for some integer $j$, and

$$\begin{array}{rl}D& =pk+q\\ & =pk+pj\\ & =p(k+j)\end{array}$$

thus $D$ is divisible by $p$.

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

$$\begin{array}{rl}D& =pk+q\\ & =pk+pj+r\\ & =p(k+j)+r\end{array}$$

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

Thus $D=pk+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},\dots ,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{array}{rlrl}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{array}$$

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{array}{rl}D& =9k+S\\ & =3\cdot 3k+S\\ & =3j+S\end{array}$$

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