Proof of the Divisibility Rules for 3 and 9
Theorem
If the sum of all the digits is a multiple of $3$, the number is a multiple of $3$; if it is a multiple of $9$, the number is a multiple of $9$.
Explanation
For example,
- $8142$ is a multiple of $3$ since $8142=3 \cdot 2714$, and indeed $8+1+4+2=15$ is a multiple of $3$.
- $1945125$ is a multiple of $9$ since $1945125=9 \cdot 216125$, and indeed $1+9+4+5+1+2+5=27$ is a multiple of $9$.
Divisibility rules have, in modern times, lost much of their practical significance, but they remain interesting tools. Multiples of $2,4,5,8$ are very easy to test, but numbers such as $3, 7, 9, 11$ require separate proofs. Fortunately, except for 7, the proofs are generally easy both to carry out and to understand.
Proof
Strategy: The key to the proof is to split powers of 10 into 1 and 99..99 so that only the digit in each place needs to be considered. For convenience in the proof, this post will use the following notation.
$$ [a_{n} a_{n-1} … a_{1} a_{0}]= a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} $$ For example, $5714$ can be expressed as follows. $$ [5714]=5000+700+10+4=5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} $$ If the proof is hard to follow, it helps to think it through with an actual example.
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \\ =& a_{n} \cdot \left( 10^{n} -1 \right) + a_{n-1} \cdot \left( 10^{n-1} -1 \right) + \cdots + a_{1} \cdot \left( 10^{1} -1 \right) \\ & + a_{0} +\left( a_{n} + a_{n-1} +…+ a_{1} \right) \\ =& \sum_{k=1}^{n} a_{k} \left( 10^{k} - 1 \right) + \sum_{k=0}^{n} a_{k} \end{align*} $$
Here $10^{n} -1=[99…99]$ is a multiple of $3$ and $9$ (for example, $10^{3} -1=999$). Therefore, if $\displaystyle \sum_{k=0}^{n} a_{k}$ is a multiple of 3, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of 3. Likewise, if $\displaystyle \sum_{k=0}^{n} a_{k}$ is a multiple of 9, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of 9.
■