Divisibility Criteria

You may already have been told how to tell when a number is divisible by $3$ or $9$: you add up the digits of the number and ask whether the sum of the digits is divisible by $3$ or $9$. For example, $$3\mid 1+1+3+1 \Rightarrow 3\mid 1131.$$ We actually have a theorem: let $n\in \Bbb N$, where $n$ can be expressed in base $10$ as $n=a_k a_{k-1} \cdots a_1 a_0$. (Here $a_0,a_1,\cdots,a_{k-1},a_k$ represent different digits, and they are not being multiplied together.) Then $$m=a_0+a_1+\cdots+a_{k-1}+a_k \Rightarrow n \equiv_3 m.$$
My approach to proving this theorem is first to express $n$ as $a_0+10a_1+\cdots+10^{k-1}a_{k-1}+10^ka_k$. We now look at some specific cases of this theorem: consider $n$ as a two-digit number. Then $n=a_0+10a_1$ and $m=a_0+a_1$. Observe that $n-m=9a_1$. Since $9a_1\equiv_9 0$, we have $n\equiv_9 m$. Now, consider $n$ as a three-digit number: $$\begin{align}n&=a_0+10a_1+10^2a_2\\ m&=a_0+a_1+a_2\\ n-m&=9a_1+99a_2\\ n&\equiv_9 m.\end{align}$$ Do you see a pattern? Is it clear to you now why the sum of digits works? This works because $10^k-1$ is a multiple of $9$: $$\begin{align}\vdash 10^k-1&\equiv_9 0\\ 10&\equiv_9 1\\ 10^k&\equiv_9 1^k\\ 10^k-1&\equiv_9 0\qquad\Box \end{align}$$ But then the question requires us to prove $n \equiv_3 m$. We actually have something stronger! Let us go ahead and prove that $\equiv_9\; \Rightarrow \; \equiv_3$. $$\begin{align}\vdash a\equiv_9 b &\Rightarrow a\equiv_3 b\\ a\equiv_9 b &\Rightarrow 9\mid (a-b)\\ &\Rightarrow 3\cdot 3\mid (a-b)\\ &\Rightarrow a-b=3\cdot 3k \quad \exists k\in \Bbb Z\\ &\Rightarrow a-b=3\cdot p \quad \exists p\in \Bbb Z\\ &\Rightarrow 3\mid (a-b) \\ &\Rightarrow a\equiv_3 b\qquad\Box \end{align}$$ We also have $\equiv_8\; \Rightarrow\; \equiv_4 \wedge \equiv_2$. We can generalise these results as $\equiv_n\; \Rightarrow\; \equiv_{\;\text{factors of n except 1}}$. It is still not the time to put this problem away. We can ask ourselves: are there extensions of this result? Are there related theorems provable using the same technique? Up to this point, we know when a number is divisible by $2,3,5,9$. What about the cases for $4,6,7,8$? Since we are still dealing with numbers in base $10$, we can modify our $10^k-1$ argument to $10^k-c^k$ for $c=4,6,7,8$. Observe that $$10^k\equiv_4 6^k\\ 10^k\equiv_6 4^k\\ 10^k\equiv_7 3^k\\ 10^k\equiv_8 2^k.$$ The key idea is to change the coefficients of the digits into powers of $c$. We state without proofs the followings: $$m=a_0+6a_1+\cdots+6^{k-1}a_{k-1}+6^ka_k \Rightarrow n \equiv_4 m\\ m=a_0+\color{blue}{2}a_1+\cdots+\color{blue}{2}^{k-1}a_{k-1}+\color{blue}{2}^ka_k \Rightarrow n \equiv_4 m\\ m=a_0+4a_1+\cdots+4^{k-1}a_{k-1}+4^ka_k \Rightarrow n \equiv_6 m\\ m=a_0+3a_1+\cdots+3^{k-1}a_{k-1}+3^ka_k \Rightarrow n \equiv_7 m\\ m=a_0+2a_1+\cdots+2^{k-1}a_{k-1}+2^ka_k \Rightarrow n \equiv_8 m.$$ You may then ask: when can we use these results? Here is an example. Say we want to divide $110$ by $7$. Using the above result and without resorting to division algorithm, we know that the remainder is $5$ because $110 \equiv_7 12 \equiv_7 5$. Here $12=3+3^2$ is our $m$. The 'beauty' of this result is that we are reducing a division problem into an addition problem! (Alternatively, we can argue that $110 \equiv_7 11\cdot 10 \equiv_7 4\cdot 3 \equiv_7 12 \equiv_7 5$ to have the same result.) There may still be something interesting about this theorem. Are there any applications if we switch to other number systems like hexadecimal or binary (by changing $n$)? Is there a relationship between modular arithmetic and change of base? Further extensions of the theorem: divisibility by $11,12,\cdots,n$?

More to read:
Fun With Modular Arithmetic

Reference:
Number Theory Through Inquiry by David C. Marshall, Edward Odell, and Michael Starbird