¿Por qué todos los "trucos de divisibilidad" parecen usar combinaciones lineales y hay alguno que no lo haga?

No, las pruebas de divisibilidad no están restringidas a formas lineales . Como se explica aquí y aquí, la regla para sacar nueves:$\,9\mid 10a+b\!\iff\! 9\mid a+b\,$se extiende a un grado superior como$\,9\mid p(10)\!\iff\! 9\mid p(1)\,$[por$\!\bmod 9\!:\ p(10)\equiv p(1)\,],\:\!$para cualquier polinomio$p(x)$con coeficientes enteros (por$\rm\color{#0a0}{PCR}$abajo). Cuando$\,n = p(10)\,$entonces$p(1)$es la suma de los dígitos decimales de$n$. Similarmente$\,11\mid 10a\!+\!b\!\iff\! 11\mid a\!-\!b\,$se extiende a$\,11\mid p(10)\!\iff\! 11\mid p(-1) =$suma de dígitos alternos.

Las pruebas comunes a las que se refiere corresponden a formas inversas de las pruebas de divisibilidad anteriores, por ejemplo$\bmod 17\!:\ 10a+b\equiv 0 \!\iff\!$ $10(a+b\color{#c00}{/10})\equiv 0\!\iff\!$ $a\color{#c00}{-5}b\equiv 0\,$por$\,\color{#c00}{1/10\equiv -5},\,$es decir, surge a través de la escala por$\,\color{#c00}{10^{-1}\equiv -5}.\,$Del mismo modo, si$\,\deg p = k\,$luego escalando por$(-5)^k\equiv 10^{-k}$cambia todos los poderes de$10$en$\,p(10)\,$en poderes de$-5$, invirtiendo efectivamente el coef, por ejemplo, para un cuadrático

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

de este modo$\,\color{#c00}{17}\mid p(\color{#c00}{10})\!\iff\! 17\mid\tilde p(\color{#c00}{-5}) =\,$poli invertido en radix$-5,\,$por$\,\color{#c00}{10(-5)\equiv_{17} 1},\,$p.ej

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

Tal radix reciprocidad divisibilidad por$\,d\,$existen pruebas para cualquier radis$r_1,\, r_2$siendo recíproco$\!\bmod d,\,$es decir, cuando$\,r_1 r_2\equiv 1,\,$por ejemplo, para binario$\,r_2\!:\ \color{#0a0}{10(2)\equiv_{19} 1}$y$\,\color{#c00}{10(-2)\equiv_{21} 1},\,$entonces

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

Este es solo uno de los numerosos ejemplos de inferencias de divisibilidad de grado superior que son omnipresentes en la teoría de números y el álgebra. Tales inferencias se vuelven obvias una vez que uno domina las congruencias y la aritmética modular (ver esp.$\rm\color{#0a0}{PCR}$= Regla de congruencia de polinomios , es decir$\,a\equiv b\Rightarrow p(a)\equiv p(b)).\,$

Consulte aquí para obtener más información sobre polinomios inversos (recíprocos), y aquí para ver una aplicación similar.

Nota La razón por la que estas pruebas de divisibilidad se pueden expresar como iteraciones de operaciones lineales es porque así es como se pueden generar polinomios (forma de Horner anidada), por ejemplo

$$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$$

es decir, los polinomios se pueden generar iterando operaciones lineales$\,f_{n+1} = c_{n+1}+ x f_n,\,$por lo que cualquier operación polinomial (por ejemplo, evaluación$\!\bmod d$) se puede realizar recursivamente aprovechando este proceso de generación inductiva (ver inducción estructural ).

De esta forma, la evaluación recursiva$\!\bmod d\,$de un polinomio (representación de un número entero en notación radix) conduce a una prueba universal de divisibilidad por$\,d,\,$que funciona modificando repetidamente los fragmentos principales de dígitos$\!\bmod d\,$(como la división a mano pero ignorando los cocientes). Sus pruebas pueden verse como una forma inversa de dicha prueba. La forma directa tiene la ventaja sobre la forma invertida de que produce el resto exacto, por lo que puede usarse para mucho más que solo pruebas de divisibilidad.

Usemos la prueba universal directa para calcular$\, 43211\bmod 7.\,$El algoritmo consiste en reemplazar repetidamente los primeros dos primeros dígitos$\rm\ \color{#0a0}{d_n\ d_{n-1}}\ $por$\rm\, \color{#0a0}{(\color{#000}3\, d_n + d_{n-1})}\bmod 7,\,$desde$\,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\ \,$$

Por eso$\rm\ 43211\equiv 0\pmod{\!7},\,$en efecto$\rm\ 43211 = 7\cdot 6173.\:$En general, la aritmética modular es más simple si usamos residuos de menor magnitud , por ejemplo$\rm\, \pm\{0,1,2,3\}\ \:(mod\ 7),\,$al permitir dígitos negativos , por ejemplo aquí . Tenga en cuenta que para el módulo$11$o$9\:$el método anterior se reduce a las bien conocidas pruebas de divisibilidad por$11$o$9\:$(también conocido como "lanzar nueves" para el módulo$9$).

Podemos inventar "trucos de divisibilidad" que no tengan esta propiedad. Por ejemplo:

"Para probar si$n$es divisible por$3$, escribir$n$como$10q+r$. Entonces, calcula$q^3 + r^3$y ver si esto es divisible por$3$."

Esto funciona debido al pequeño teorema de Fermat: para todos los números enteros$a$y primos$p$,$a^p \equiv a \pmod p$. En particular,$q^3 \equiv q \pmod3$y$r^3 \equiv r\pmod3$, entonces$q^3+r^3 \equiv q + r \equiv 10q+r \pmod 3$.

¡Este no es un buen truco! No porque no funcione, sino porque revisando$q^3+r^3$para la divisibilidad por$3$es probablemente más difícil que comprobar$n$era.

Sin embargo, en casos muy específicos, podríamos aprovechar este tipo de truco. Por ejemplo, si se enfrenta a tratar de averiguar si$10000256$es divisible por$7$, podría ser útil darse cuenta de que$10000256 = 10^7 + 2 \cdot 2^7$, por lo que es congruente con$10 + 2 \cdot 2 = 14$módulo$7$.

No diría que, en general, es cierto que estas reducciones lineales preservan la divisibilidad; se están tomando decisiones específicas para que eso funcione. Para la primera relación, donde$n=10q+r$:

$$q-5r = q-5(n-10q) = 51q-5n\equiv-5n\;\text{(mod 17)}.$$ Entonces$q-5r$es divisible por$17$si y si$n$es divisible por$17$. La clave es la desaparición del término extra (en este caso,$51q$) cuando se trabaja en módulo$17$. Esto no puede suceder con una expresión que es cuadrática en$q$y lineal en$r$...$r$es lineal en$q$y$n$, por lo que no hay novedades$q^2$término para cancelar el que está comenzando. Eso deja de lado el hecho de que este tipo de método solo es útil si los valores son cada vez más pequeños... pasando de$n=10q+r$a$|6q^2-5r|$, por ejemplo, no tiene esa garantía.