Comprobar la divisibilidad por grandes cantidades

Question

Actualmente estoy familiarizado con el método de la comprobación de si un número es divisible por $2$, $3$, $4$, $5$, $6$, $8$, $9$, $10$, $11$. Sin embargo hay una forma de comprobar si un no es divisible por $23$ ?

He leído algo en este enlace respecto a este asunto, pero realmente no podía entender lo que el autor está tratando de decir. Cualquier ayuda en este sentido se agradece. Gracias.

Answer 1

Aquí está la explicación a ese enlace:

Sabemos que $10 \cdot 7 = 70 \equiv 1 \mod 23$$3 \cdot 23 = 69$.

Por lo tanto, si tenemos en cuenta $10a + b \mod 23$ y se nota que la $7$ es coprime a$23$, $10a + b \equiv 0 \mod 23 \iff 7(10a + b) = 70a + 7b \equiv a + 7b \equiv 0 \mod 23$

Y es que ¿cómo consiguió ese $10a + b$ es divisible por $23$ fib $a + 7b$ es divisible por $23$. Y esto permite que el blogger deshacerse de un dígito, más o menos, en cada paso para comprobar fácilmente la divisibilidad.

Answer 2

La idea detrás de "todas esas comprobaciones" es mirar a la divisibilidad por informática el número que desea comprobar la divisibilidad módulo del divisor. Por ejemplo, el truco para el cómputo de divisibilidad por $11$ todo se reduce a $$ un \times 10^3 + b \times 10^2 + c \times 10 + d \equiv -a + b - c + d \pmod{11} $$ así que usted puede mirar en el alternan suma de los números en lugar de buscar en el big one. Usted puede desarrollar una táctica similar modulo $23$, por ejemplo, ya $100 \equiv 8 \pmod {23}$, usted tiene $$ a \times 100^2 + b \times 100 + c \equiv \times 64 + b \times 8 + c \equiv \times (-5) + b \times 8 + c \pmod {23}. $$ Tal vez el truco no se ve tan bien, pero eso es porque los trucos funcionan bien cuando los números son pequeños o bastante (tales como : que es fácil mirar a la divisibilidad por $10000000000$).

Espero que ayude,

Answer 3

Sugerencia de $\rm\begin{eqnarray}\mod\ 23\!:\ \ 0&\equiv&\rm\, \ \ a\,10^3 + b\,10^2 + c\,10 + d \\ \iff\ 0 &\equiv&\rm\,(a\,10^3 + b\,10^2 + c\,10 + d)\,7^3 \\ \iff\ 0 &\equiv&\rm\ \ a\ \ \ \, +\, \, \ \ b\:7\ \, +\, \ c\:7^2 + d\ 7^3\quad by\quad 10\cdot 7\equiv 1\,\ (mod\ 23) \end{eqnarray}$

Ahora a evaluar mod $23\,$ $\rm\ a + 7\,(b + 7\,(c + 7\,d))\ $ en Horner forma como explico en detalle aquí. Este es esencialmente el universal divisibilidad de la prueba aplicada a los invierte radix polinomio. Tiene la desventaja de que, si bien correctamente las pruebas de equivalencia cero, no cede el real resto.

Answer 4

Él muestra que cualquier número entero de la forma $10a + b$ es divisible por 23 si y sólo si $a + 7b$ es divisible por 23. Así que para un número $n$ con más de un dígito, que repetidamente puede reemplazar con el número de $a + 7b$ donde $b$ es el último dígito de la $n$, e $a$ es el resto.

En su ejemplo, tenemos $n = 146096$ e se puede escribir como $10 \cdot 14609 + 6$, es decir,$a = 14609$, $b = 6$, y, por tanto, $n$ es divisible por 23 si y sólo si $7a + b = 7 \cdot 14609 + 6 = 14651$ es. Y acabamos de repetir este proceso hasta que tenemos un pequeño número suficiente.

Como se puede ver, esta no es una práctica de la prueba, ya que nos queda para hacer multiplicaciones.