Why do all "divisibility tricks" seem to use linear combinations, and are there any that don't?

Question

When I say "divisibility trick" I mean "a recursive algorithm designed to show that, after multiple iterations, if the final output is a multiple of the desired number, then the original was also a multiple of the same number." Here's an example for a divisibility trick for 17.

Rewrite $n$ as $10q+r$, with $r<10$. Then, evaluate $|q-5r|$. Repeat this process until left with an easily factorable number.

Here's another.

Rewrite $n$ as $100q+r$, with $r<100$. Then, evaluate $|r-2q|$. Repeat this process until left with an easily factorable number.

Just to show these both work (or, at least, work for one particular number, let's try both on $31382$.

METHOD ONE: $31382\rightarrow3128\rightarrow272\rightarrow17$, ergo $17\ |\ 31382$.

METHOD TWO: $31382\rightarrow544\rightarrow34$, ergo $17\ |\ 31382$.

These divisibility tricks rely on breaking the number down into groups of digits and applying some linear operation to them. However, when we try to use a non-linear function, things seem to break down. For example, much as how method one here draws off the fact that $17\ |\ 51$ and the second relies off of $17\ |\ 119$, let's try to do something with $17\ |\ 34$. Namely:

Rewrite $n$ as $10q+r$, with $r<10$. Then, evaluate $|6q^2-5r|$. Repeat this process until left with an easily factorable number.

We can try this with $34$ and see, yes, $6(9)-5(4)=34$, so $17\ |\ 34$. But this fails for most numbers. For $51$, we have $51\rightarrow145$, and it diverges from there (also note that $17\not|\ 145$). Even with $17$, which is obviously a multiple of $17$, we have $17\rightarrow29$.

What separates the wheat from the chaff here, so to speak? Why is it that if we break down the digits of the multiple of some prime and make a linear relation around it, it seems to be true for all other multiples of the prime, but the same doesn't work for, say, a quadratic relation?

Answer 1

No, divisibility tests are not restricted to linear forms. As explained here & here the rule for casting out nines: $\,9\mid 10a+b\!\iff\! 9\mid a+b\,$ extends to higher degree as $\,9\mid p(10)\!\iff\! 9\mid p(1)\,$ [by $\!\bmod 9\!:\ p(10)\equiv p(1)\,],\:\!$ for any polynomial $p(x)$ with integer coef's (by $\rm\color{#0a0}{PCR}$ below). When $\,n = p(10)\,$ then $p(1)$ is the sum of the decimal digits of $n$. Similarly $\,11\mid 10a\!+\!b\!\iff\! 11\mid a\!-\!b\,$ extends to $\,11\mid p(10)\!\iff\! 11\mid p(-1) =$ alternating digit sum.

The common tests you refer to correspond to reversed forms of the above divisibility tests, e.g. $\bmod 17\!:\ 10a+b\equiv 0 \!\iff\!$ $ 10(a+b\color{#c00}{/10})\equiv 0\!\iff\!$ $ a\color{#c00}{-5}b\equiv 0\,$ by $\,\color{#c00}{1/10\equiv -5},\,$ i.e. it arises via scaling by $\,\color{#c00}{10^{-1}\equiv -5}.\,$ Similarly, if $\,\deg p = k\,$ then scaling by $(-5)^k\equiv 10^{-k}$ changes all powers of $10$ in $\,p(10)\,$ into powers of $-5$, effectively reversing the coef's, e.g. for a quadratic

$\ \ \ \bmod \color{#c00}{17}\!:\,\ \ 0\equiv \overbrace{a\:\!10^2+b\:\!10+c}^{\large p(\color{#c00}{10})} \overset{\times\ (\color{c00}{-5})^{\large 2}\!\!}\iff\ \overbrace{0\equiv c(-5)^2+b(-5)+a}^{\large \tilde p(\color{#c00}{-5})}$

thus $\,\color{#c00}{17}\mid p(\color{#c00}{10})\!\iff\! 17\mid\tilde p(\color{#c00}{-5}) =\,$ reversed poly in radix $-5,\,$ by $\,\color{#c00}{10(-5)\equiv_{17} 1},\,$ e.g.

$$ \color{#c00}{17}\mid 901\,\ \ {\rm by}\ \ 17\mid 109_{\color{#c00}{-5}} = 1(\color{#c00}{-5})^2+0(\color{#c00}{-5})+9 = 34 \quad$$

Such radix reciprocity divisibility by $\,d\,$ tests exist for any radices $r_1,\, r_2$ being reciprocal $\!\bmod d,\,$ i.e. when $\,r_1 r_2\equiv 1,\,$ e.g. for binary $\,r_2\!:\ \color{#0a0}{10(2)\equiv_{19} 1}$ and $\,\color{#c00}{10(-2)\equiv_{21} 1},\,$ so

$$\begin{align} &\color{#0a0}{19}\mid 912\,\ \ {\rm by}\ \ 19\mid219_{\,\color{#0a0}2} \, =\ 2\,(\color{#0a0}2)^2\ +\ 1\,(\color{#0a0}2)\ +\ 9 = 19\\[.4em] &\color{#c00}{21}\mid 924\,\ \ {\rm by} \ \ 21\mid 429_{\color{#c00}{-2}}= 4(\color{#c00}{-2})^2+2(\color{#c00}{-2})+9 = 21\end{align}\quad $$

This is but one of numerous examples of higher-degree divisibility inferences that are ubiquitous in number theory and algebra. Such inferences become obvious once one masters congruences and modular arithmetic (see esp. $\rm\color{#0a0}{PCR}$ = Polynomial Congruence Rule, i.e. $\,a\equiv b\Rightarrow p(a)\equiv p(b)).\,$

See here for more on reverse (reciprocal) polynomials, and here for a similar application of such.

Note $ $ The reason that these divisibility tests can be expressed as iterations of linear operations is because that is how polynomials can be generated (nested Horner form), e.g.

$$ a_0 + a_1 x + a_2 x^2 + a_3 x^3 =\, a_0 + x(a_1 + x (a_2 + x(a_3)))\qquad$$

i.e. polynomials can be generated by iterating linear operations $\,f_{n+1} = c_{n+1}+ x f_n,\,$ so any polynomial operation (e.g. evaluation $\!\bmod d$) can be performed by recursively piggy-backing on this inductive generation process (see structural induction).

In this way, recursive evaluation $\!\bmod d\,$ of a polynomial (representation of an integer in radix notation) leads to a universal test for divisibility by $\,d,\,$ that works by repeatedly modding out leading chunks of digits $\!\bmod d\,$ (like longhand division but ignoring quotients). Your tests can be viewed as a reversed form of such a test. The forward form has the advantage over the reversed form that it yields the exact remainder so it can be used for much more than just divisibility testing.

Let's use the forward universal test 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,\,$ since $\,10d_n+d_{n-1}\equiv 3d_n+d_{n-1}\pmod{\!7}$

$$\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$).

Answer 2

We can invent "divisibility tricks" that don't have this property. For example:

"To test if $n$ is divisible by $3$, write $n$ as $10q+r$. Then, compute $q^3 + r^3$ and see if this is divisible by $3$."

This works because of Fermat's little theorem: for all integers $a$ and primes $p$, $a^p \equiv a \pmod p$. In particular, $q^3 \equiv q \pmod3$ and $r^3 \equiv r\pmod3$, so $q^3+r^3 \equiv q + r \equiv 10q+r \pmod 3$.

This is not a good trick! Not because it doesn't work, but because checking $q^3+r^3$ for divisibility by $3$ is probably harder than checking $n$ was.

In highly specific cases, we might be able to take advantage of this kind of trick, though. For example, if you are faced with trying to figure out if $10000256$ is divisible by $7$, it might help to realize that $10000256 = 10^7 + 2 \cdot 2^7$, so it is congruent to $10 + 2 \cdot 2 = 14$ modulo $7$.

Answer 3

I wouldn't say that it's generally true that these linear reductions preserve divisibility; specific choices are being made for that to work out. For the first relation, where $n=10q+r$: $$ q-5r = q-5(n-10q) = 51q-5n\equiv-5n\;\text{(mod 17)}. $$ So $q-5r$ is divisible by $17$ iff $n$ is divisible by $17$. The key is the vanishing of the extra term (in this case, $51q$) when working modulo $17$. This can't happen with an expression that is quadratic in $q$ and linear in $r$... $r$ is linear in $q$ and $n$, so there is no new $q^2$ term to cancel out the one you're starting with. That's leaving aside the fact that this kind of method is only helpful if the values are getting smaller... going from $n=10q+r$ to $|6q^2-5r|$, for instance, doesn't have that guarantee.