Si está buscando un patrón que le dé una regla de divisibilidad para cualquier número, no busque más que el valor del número mod 10.
Para cualquier número que sea producto de múltiples poderes primos diferentes, solo puede realizar la regla de divisibilidad para cada poder primo, y la divisibilidad por su producto se establecerá si todos estos tienen éxito. Entonces, por ejemplo, un número es divisible por 6 si la divisibilidad verifica que 2 y 3 tengan éxito.
Entonces, solo necesitamos una forma de generar reglas para cualquier potencia principal.
Como 2 y 5 son ambos 0 (mod 10), tienen reglas especiales. A saber, que un número es divisible por 2 ^ k o 5 ^ k si los últimos k dígitos, tomados como un número, son divisibles por 2 ^ k o 5 ^ k. Esto se deduce del hecho de que 10 ^ k siempre es divisible por 2 ^ k y 5 ^ k.
El resto de los residuales mod 10 (a saber, 1, 3, 7 y 9) son relativamente primos a 10, lo que significa que podemos dividir el número que estamos probando por 10 sin revocar su divisibilidad por la potencia principal que tengamos ‘ re interesado en; si antes era divisible por 17, seguirá siendo divisible por 17 después de dividirlo por 10.
¡Lo que significa que podemos dividir por 10 repetidamente hasta obtener un número lo suficientemente pequeño como para verificar su divisibilidad de un vistazo! Y dividir por diez es tan simple como cortar ceros al final del número, ¡por lo que ni siquiera tenemos que hacer ningún cálculo real!
Si las cosas fueran tan fáciles, ¿verdad? Desafortunadamente, el número que estamos probando puede no ser divisible por 10, lo que significa que no hay cero al final para cortar. Entonces, ¿cómo podemos obtener un número que sea divisible por 10? ¡Podemos restar el último dígito y obtendremos un número divisible por 10! Pero … (por supuesto, hay un pero …) restar un número arbitrario del número cambiará el módulo; podría no ser divisible por 17 después, incluso si lo fuera antes.
¡Todo no esta perdido! Si podemos averiguar exactamente cómo restar ese número cambia el módulo y hacer algo que deshaga ese cambio de inmediato mientras aún nos deja con un número que es un múltiplo de 10, podemos continuar con nuestro programa de corte de dígitos sin problemas.
Así que aquí está el plan: multiplicaremos el dígito que estamos restando por un múltiplo de 10 para que el resultado tenga un módulo exactamente igual al módulo que estamos restando, y agregaremos este nuevo número al múltiplo de 10 conseguimos restando el dígito. El resultado también será un múltiplo de 10 (ya que es una suma de múltiplos de 10), pero será divisible por n si (y solo si) el número original era divisible por n, porque los cambios en el módulo en la resta y la adición se cancela exactamente entre sí.
Por ejemplo, queremos probar la divisibilidad del número 3094 por 27. Necesitamos convertir 3094 en un múltiplo de 10, por lo que restamos cuatro, produciendo 3090. Esto reduce su resto mod 27 por cuatro, por lo que multiplicamos los cuatro eliminamos por -80, produciendo -320, que es igual a (-12 * 27 + 4). En otras palabras, es congruente con 4 (mod 27), lo que significa que si lo agregamos, aumentaremos el resto del mod 27 en 4. Esto compensa exactamente la resta en cuatro que hicimos en el paso anterior. El resultado de la suma es 2770, que es un múltiplo de 10, y es un múltiplo de 27 si y solo si 3094 fue. Ahora, podemos dividirlo por 10 para obtener el número 277. Podemos decir de un vistazo que este número no es divisible por 27 (porque es 7 más que 27 * 10), así que hemos terminado; 3094 no es divisible por 27.
Entonces, la única pregunta que queda es la siguiente: ¿Cómo sabemos qué número multiplicar en ese segundo paso? ¿Cómo supe elegir -8?
Volvamos y veamos los residuos que aún no sabemos cómo manejar: 1,3,7 y 9. Dado que estos números son relativamente primos a 10, algunos múltiplos de cada uno producirán un número que es 1 o -1 (mod 10). Estos son los residuos más fáciles de trabajar y nos permiten generar reglas con facilidad. ¿Por qué? Porque, cuando se considera mod cualquier número que sea 1 o -1 mod 10, multiplicar por 10 es como multiplicar por 1 o -1 respectivamente. Es decir, en el primer caso, multiplicar por 10 no cambia su resto, mientras que en el último caso, simplemente intercambia su signo.
Como ejemplo, dejemos que nuestro módulo sea 9. Dado que 10 es 1 (mod 9), multiplicar por 10 es como multiplicar por 1 (mod 9). Por ejemplo: 1 es 1 (mod 9). 10 es 1 (mod 9). 100 es 1 (mod 9) (= 9 * 11 + 1). 1000 es 1 (mod 9) (= 9 * 111 + 1).
O como otro ejemplo, dejemos que nuestro módulo sea 11. Dado que 10 es -1 (mod 11), multiplicar por 10 es como multiplicar por -1 (mod 11). Por ejemplo: 1 es 1 (mod 11). 10 es -1 (mod 11). 100 es 1 (mod 11) (= 9 * 11 + 1). 1000 es -1 (mod 11) (= 91 * 11-1).
Entonces, ¿recuerdas cuál fue el segundo paso en el proceso de acortamiento del número de prueba? Multiplique el dígito eliminado por un múltiplo de 10 que da como resultado un número con exactamente el mismo módulo exacto que el dígito eliminado. Si tuviéramos un múltiplo de 10 que se sabía que era congruente con 1 (mod n), entonces simplemente multiplicaríamos por este múltiplo, sabiendo que es lo mismo que multiplicar nuestro dígito por 1, y así obtendremos el módulo correcto. Si tuviéramos un múltiplo de 10 que se sabía que era congruente con -1 (mod 10), podríamos simplemente multiplicar por el opuesto de este múltiplo, y saber que nuevamente es lo mismo que multiplicar nuestro dígito por 1, y que nuevamente producirá el módulo correcto.
Para los divisores que terminan en 1 o 9, el múltiplo correcto de 10 es obvio: estos números son directamente adyacentes a un múltiplo de 10, por lo que utilizaremos este (o su opuesto). Por ejemplo, para 29, usamos 30, y para 61, usamos -60 (negativo, porque 10 es -1 (mod 61)).
Para los divisores que terminan en 3 o 7, se puede obtener el múltiplo correcto multiplicando primero el divisor por 3, dando así un número que termina en 9 o 1. Por lo tanto, para 13, usamos 40 (porque es adyacente a 3 * 13 = 39), y para 17, usamos -50 (porque 3 * 17 = 51).
Observe que el múltiplo más cercano de diez para 3,9 y 11 es 10 en sí. Esto significa que ni siquiera tenemos que multiplicar el dígito que cortamos por nada (excepto -1, en el caso de 11) cuando lo cambiamos para agregarlo a los dígitos restantes. Como resultado, podemos sumar todos los dígitos a la vez para hacer la reducción en un gran paso (usando una suma alterna en el caso de 11 para tener en cuenta el hecho de que multiplicaría por -1 al cambiar al siguiente dígito ) Nunca será tan bueno para ningún otro divisor.
Ahora que se describe el algoritmo, hagamos un ejemplo. Verifiquemos si 4913 es divisible por 17. Como se mencionó anteriormente, el quinto múltiplo de 10 es -1 (mod 17), por lo que multiplicaremos por -5 en el segundo paso.
Primero, cortamos el último dígito, lo que significa restar simultáneamente 3 (que cambia el módulo) y dividir por 10 (que mantiene la divisibilidad). Luego, multiplicamos el 3 por -5 para obtener -15, y agregamos esto a la parte restante de 491 (cambiando así el módulo). 491-15 = 476.
Repetimos el proceso. Corta los 6 dejando 47. 6 * -5 = -30. 47-30 = 17. Obviamente, 17 es divisible por 17, entonces 4913 también debe serlo. (De hecho, 4913 = 17 ^ 3.)
Una nota: este proceso no se puede utilizar para averiguar fácilmente cuál es el resto en el caso de que el número de prueba NO sea divisible por el divisor. Esto se debe a que dividir por 10 cambiará el módulo en este caso. Para saber cuál sería el resto, uno debe realizar un seguimiento de cuántos pasos de reducción realizó antes de que el resto del resultado fuera obvio, y luego multiplique repetidamente ese resto, mod n, por 10. (O, en el caso de división por 7, se multiplicará por 3, como 10 = 3 (mod 7).) Sin embargo, uno PUEDE usar el método de suma de dígitos para determinar el resto de un número mod 3 o 9 por las razones indicadas anteriormente. Del mismo modo, uno puede usar la suma de dígitos alternos para encontrar el resto del mod 11, siempre que comience haciendo el dígito más a la derecha POSITIVO.