The Proof of the Divisibility Test for 7 and 13
Buildup
In this post, for convenience in discussing number systems, we 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 represented as follows. $$ \begin{align*} [5714] =& 5000+700+10+4 \\ =& 5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} \end{align*} $$
Theorem
$$ a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} $$ If it’s a multiple of $7$, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of $7$, $$ a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} $$ If it’s a multiple of $13$, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of $13$.
Explanation
What this means is, if the number obtained by grouping digits in threes and alternately adding and subtracting them is a multiple of $7$, then the original number is also a multiple of 7. Let’s understand this with an example.
For instance, looking at $745444$, according to the rule, $$ 745-444=7 \cdot 301 $$ it’s a multiple of 7, and indeed $745444$ is a multiple of $7$ as it is $745444=7 \cdot 106492$. Even for a larger number like $11794545$, the rule above still applies, $$ -11+794-545 = 238 = 7 \cdot 34 $$ is a multiple of $7$, and indeed $11794545$ is $11794545=7 \cdot 1684935$ which makes it a multiple of $7$.
This theorem holds true for the case of $13$ as well, and actually also for the case of $11$. The reason is because the multiple determination rule for $7$, $11$, and $13$ all come from the same proof. Merely changing the numbers results in exactly the same proof, so we will omit the case of $11$ and $13$.
Proof
Strategy: The proof itself uses only very basic techniques, but because it’s inherently lengthy and requires an idea, it’s not easy. A key idea is using the fact that $1001$ and $999999$ are multiples of $7$. $$ 10^{3} +1=1000+1=1001=7\cdot 143 \\ \left( 10^{3} +1 \right) \left( 10^{3} -1 \right) = 10^{6} -1=1000000-1=999999=7\cdot 142857 $$
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& [a_{n} a_{n-1} a_{n-2} ]10^{n-2} +[a_{n-3} a_{n-4} a_{n-5}]10^{n-5} +…+[a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}] \\ =& ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}]) \end{align*} $$
Focusing only on the part inside the parentheses,
$$ \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) \\ &= {[a_{n} a_{n-1} a_{n-2}]10^{3} +([a_{n} a_{n-1} a_{n-2}]-[a_{n} a_{n-1} a_{n-2}])+[a_{n-3} a_{n-4} a_{n-5}]} \\ &= {([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n} a_{n-1} a_{n-2}])- ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= {[a_{n} a_{n-1} a_{n-2}]1001-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) \end{align*} $$
Thus, $$ ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) $$ If it’s a multiple of $7$, $$ [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] $$ is also a multiple of $7$. Let’s now generalize it.
$$ \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} -([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \end{align*} $$
If we group terms like $[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5}$ all together as $c$,
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*} $$
Regardless of what $c$ is, since $7c$ is definitely a multiple of $7$, the proof is complete if the latter part is a multiple of $7$. And here, the property of $999999$ is used.
$$ \begin{align*} A 10^{6} &=A 10^{6} -A+A \\ &=( 10^{6} -1)A+A \\ &=999999A+A \\ &=7\cdot 142857A+A \\ &=7c+A \end{align*} $$
Since the above equation holds, the power of $10$ will yield a constant term divisible by $7$, reducing the degree by $6$ each time.
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*} $$
In the above equation, all instances of $n-5, n-11, … ,0$ are multiples of $6$, thus
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])+…+([a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]) \end{align*} $$
Therefore,
$$ [a_{n} a_{n-1} a_{n-2}]- [a_{n-3} a_{n-4} a_{n-5}]+…+[a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}] $$
If it’s a multiple of $7$, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of $7$.
Considering the point of $1001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13$, whether it’s the case of $11$ or $13$, the proof is virtually complete.
■