Why do all "divisibility tricks" seem to use linear combinations, and are there any that don't? 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?
 A: 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.
A: 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$.
