📂Number Theory

A Simpler Proof of the Divisibility Test for 11

Buildup

In this post, we use the following notations for convenience regarding numerical bases. $$[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

If $a_{n} - a_{n-1} + … + a_{1} - a_{0}$ is a multiple of $11$, then $[a_{n} a_{n-1} … a_{1} a_{0}]$ is also a multiple of $11$.

Explanation

Of course, from the divisibility rules of $7$ and $13$, we can determine whether a given number is a multiple of $7$, $11$, $13$, but in the case of $11$, there is a much easier result and a simple proof. However, unlike the cases of $7$, $11$, $13$, it uses congruences, so a very basic knowledge of number theory is required to understand the proof.

Proof

Strategy: The key idea used in the proof is that under modulo $11$, $10$ and $-1$ are congruent. With just this hint, the proof is practically done. $$10 \equiv -1 \pmod {11}$$

---

$$\begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ \equiv & a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \pmod {11} \\ \equiv & a_{n} {(-1)}^{n}+ a_{n-1} {(-1)}^{n-1}+…+ a_{1} {(-1)}^{1}+ a_{0} {(-1)}^{0} \pmod {11} \\ \equiv & a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \pmod {11} \end{align*}$$ In other words, if $a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0}$ is a multiple of $11$, then $$a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \equiv 0 \equiv [a_{n} a_{n-1} … a_{1} a_{0}] \pmod {11}$$ In other words, $[a_{n} a_{n-1} … a_{1} a_{0}]$ is a multiple of 11.

■