Sabemos que, dando un número, por la suma de cada uno de sus dígitos, y mod el resultado por 3, si el aviso es 0, entonces el número es un múltiplo de 3, de lo contrario, no.
Este algoritmo funciona para 9 también.
Me pregunto ¿hay similares algoritmos generales para comprobar otros pequeños números primos, por ejemplo 7 o 11?
O, simplemente, que 3 y 9 son demasiado especiales?
Un número escrito con los dígitos $d_n\ldots d_2 d_1 d_0$ en notación decimal significa $$ 10^n d_n + \cdots + 10^2 d_2 + 10^1 d_1 + d_0 $$
Divisibility tests are generally based on working modulo the divisor and correcting for the effect of the $10^n$ factors of the sum.
Dividing by $3$ and $9$ are special because $10\equiv 1$ modulo $3$ or $9$, so the $10^n$ factors disappear completely. These are the only divisors with this property (except for $1$, which is trivial). For all other divisors, different digit positions contribute differently to the sum, and the divisibility rules are correspondingly more complicated to state.
(Well, actually the divisibility rules for $2$ and $5$ are even simpler because $10\equiv 0$ modulo $2$ or $5$, so all terms in the sum above except for $d_0$ vanish completely and you need only to look at the last digit).
In other bases than ten, say, base $b$, it is similarly simple to test for divisibility by $b-1$ -- or divisibility by any divisor of $b-1$. In base sixteen, for example, the sum-of-digits test works for divisibility by $3$ but not for $9$ (because $9$ does not divide fifteen). But it does work for divisibility by $5$ in that setting.
If you know programming, here is pseudocode for a generic divisibility test:
// input: d[n] ... d[0] are the digits of the input number
// input: D, the divisor
b = 10 // the base
s = 0 // a running sum
w = 1 // magic sauce: note carefully what happens to this
for i = 0 to n:
s = s + w * d[i]
w = (b * w) % D
// now s is divisible by D if and only if the original number was
The nice shape of the tests for $D=3$ and $D=9$ are because in that case w = (b * w) % D is a no-op (because (b*w)%D == ((b%D)*(w%D))%D always and b%D==1) so w stays $1$ en todo el bucle, a diferencia de en otros casos.
El más complejo de pruebas de divisibilidad para otros divisores corresponden a precomputing la secuencia de ws.
La característica especial de $9$ es que es uno menos que el número de nuestros dedos (es decir, nuestra base). En otras palabras, $3\mid 10-1$. Sin embargo, $7\mid 10^6-1$, por lo que nos encontramos de un (no tan perfecto) regla: el grupo de los dígitos en grupos de seis para el final, añadir los seis números de un dígito, y comprobar si la suma es divisible por $7$ (posiblemente mediante la repetición de este procedimiento). Del mismo modo, de $11\mid 10^2-1$, podemos trabajar con grupos de dos dígitos a prueba de divisibilidad por $11$.
Por cierto, no es una simple prueba para $11$: la alternancia de suma de dígitos. Del mismo modo, se puede trabajar con la alternancia de la suma de los grupos de tres diits para $7$.
Mientras que hay abigarrado pruebas de divisibilidad derivable de $\,c\mid 10 a + b\iff c\mid ja+kb\,$ pequeña $\,j,k\,$ es generalmente más sencillo y rápido de usar sólo la aritmética modular (que, a diferencia de dichas pruebas, tiene la ventaja de computación en el resto, por lo que pueden ser utilizados para la comprobación aritmética, como en la fundición de fuera de nueves).
Este universal método de cantidades a la evaluación de una base polinomio en anidados Horner forma, usando aritmética modular. Por ejemplo, considere la evaluación de un $4$ dígitos radix $10$ número modulo $7$.
$$\begin{align} \rm\ d_3\ d_2\ d_1\ d_0 \rightarrow\ &\rm ((d_3\cdot 10 + d_2)\cdot 10 + d_1)\ 10 + d_0\\ \equiv\ &\rm (\color{#c00}{(d_3\cdot\ 3\ + d_2)}\cdot\ 3\ + d_1)\ \ 3\ + d_0\!\!\pmod{7}\end{align}\qquad$$
debido a $\rm\ 10\equiv 3\,\ (mod\,\ 7)\:.\:$, con Lo que podemos calcular el resto $\rm\ (mod\ 7)\ $ en varias ocasiones la sustitución de los dos dígitos iniciales $\rm \,d_k\,d_{k-1}\,$ $\rm \ \color{#c00}{(d_k\cdot 3 + d_{k-1})}\ {\rm mod}\ 7.\,$ Por ejemplo
$\rm\qquad\qquad\qquad\qquad\phantom{\equiv} \color{#C00}{4\ 3}\ 2\ 1\ 1$
$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad $ $\rm\quad \color{#C00}4\cdot 3 + \color{#C00}3\ \equiv\ \color{green}1 $
$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad $ $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5 $
$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3\ 5} \color{#b0f}{2\ 1}\quad $ $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{#b0f}2 $
$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad $ $\rm\quad \color{#b0f}2\cdot 3 + \color{#b0f}1\ \equiv\ 0 $
Por lo tanto $\rm\ 43211\equiv 0\:\ (mod\ 7),\:$ hecho $\rm\ 43211 = 7\cdot 6173$
Generalmente la aritmética modular es más sencillo si se utiliza un sistema equilibrado de representantes, por ejemplo, $\rm\: \pm\{0,1,2,3\}\ \:(mod\ 7)\:.$ Aviso que para el módulo de $11$ o $9\:$ el método anterior se reduce a la conocida pruebas de divisibilidad por $11$ o $9\:$ (.k.a. "echa fuera a los nueves" para el módulo de $9$).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
