Sorry if the question is old but I wasn't able to figure out the answer yet.
I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc… but how can someone derive those rules for any number $n$ let's say. I know it could be done using congruences, but how ?
Thank you !
Best Answer
We need not memorize motley exotic divisibility tests. There is a universal test that is simpler and much easier recalled, viz. evaluate a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $3$ digit radix $10$ number modulo $7$. In Horner form $\rm\ d_2\ d_1\ d_0 \ $ is $\rm\: (\color{#0a0}{d_2\cdot\color{#90f}{10} + d_1})\ 10 + d_0\ \equiv\ (\color{#0a0}{d_2\cdot 3 + d_1})\ 3 + d_0\ (mod\ 7)\ $ since $\rm\ \color{#90f}{10}\equiv\color{#0a0}3\ (mod\ 7).\:$ Hence we compute the remainder $\rm\ (mod\ 7)\ $ as follows. Start with the leading digit then repeatedly apply the operation: $\rm\color{#0a0}{multiply\ by\ 3\ then\ add\ the\ next\ digit}$, doing all of the arithmetic $\!\bmod 7$.
For example, let's use this algorithm to compute $\, 43211\bmod 7.\,$ The algorithm consists of repeatedly replacing the first two leading digits $\rm\ \color{#0a0}{d_n\ d_{n-1}}\ $ by $\rm\, \color{#0a0}{(\color{#000}3\, d_n + d_{n-1})}\bmod 7,\,$ namely
$$\begin{array}{rrl}\bmod 7\!:\ &\color{#0A0}{4\ 3}\ 2\ 1\ 1^{\phantom{|^{|}}}\!\!\!&\\ \equiv\!\!\!\! &\color{#c00}{1\ 2}\ 1\ 1 &\!{\rm by}\ \ \:\! \smash[t]{\overbrace{3\cdot \color{#0a0}4 + \color{#0a0}3}^{\rm\textstyle\color{#0a0}{\,\color{#000} 3\,\ d_n\! + d_{n-1}}\!\!\!\!\!\!\!}} \equiv\ \color{#c00}1\\ \equiv\!\!\!\! &\color{#0af}{5\ 1}\ 1&\!{\rm by}\ \ \ 3\cdot \color{#c00}1 + \color{#c00}2\ \equiv\ \color{#0af}5\\ \equiv\!\!\!\! & \color{#f60}{2\ 1}&\!{\rm by}\ \ \ 3\cdot \color{#0af}5 + \color{#0af}1\ \equiv\ \color{#f60}2\\ \equiv\!\!\!\! &\color{#8d0}0&\!{\rm by}\ \ \ 3\cdot \color{#f60}2 + \color{#f60}1\ \equiv\ \color{#8d0}0 \end{array}\qquad\qquad\quad\ \, $$
Hence $\rm\ 43211\equiv 0\pmod{\!7},\,$ indeed $\rm\ 43211 = 7\cdot 6173.\:$ Generally the modular arithmetic is simpler if we use least magnitude residues, e.g. $\rm\, \pm\{0,1,2,3\}\ \:(mod\ 7),\,$ by allowing negative digits, e.g. here. Note that for modulus $11$ or $9\:$ the above method reduces to the well-known divisibility tests by $11$ or $9\:$ (a.k.a. "casting out nines" for modulus $9$).