Reglas de divisibilidad para bases distintas de $10$

Question

Todavía recuerdo la sensación, cuando aprendí que un número es divisible por $3$ si la suma de dígitos es divisible por $3$ . La forma general de obtener estas reglas para el sistema decimal regular se pregunta/responde aquí: Reglas de divisibilidad y congruencias . Ahora me pregunto, ¿qué reglas de divisibilidad tiene un extranjero con $12$ (o $42$ ) que se le ocurra a los dedos?

Así que dejemos $n=\sum_k c_k b^k$ sea la representación con base $b$ . Algunos ejemplos indican que $n$ es divisible por $b-1$ Si $\sum_k c_k$ es. Esto parece ser una extensión pobre de la divisibilidad decimal por $9$ regla.

La respuesta a la pregunta anterior, dice que "No es necesario memorizar pruebas de divisibilidad exóticas. " . ¡Las pruebas de divisibilidad exóticas de Motley son muy bienvenidas aquí!

Answer 1

Reclamación 1:

La regla de divisibilidad de un número ' $a$ ' para ser dividido por ' $n$ ' es la siguiente. Expresar el número ' $a$ ' en la base ' $n+1$ '. Deja ' $s$ ' denotan la suma de dígitos de ' $a$ ' expresado en base ' $n+1$ '. Ahora $n|a \iff n|s$ . De manera más general, $a \equiv s \pmod{n}$ .

Ejemplo:

Antes de ponernos a demostrarlo, veremos un ejemplo de ello. Digamos que queremos comprobar si $13|611$ . Expreso $611$ en la base $14$ . $$611 = 3 \times 14^2 + 1 \times 14^1 + 9 \times 14^0 = (319)_{14}$$ donde $(319)_{14}$ denota que el número decimal $611$ expresado en base $14$ . La suma de los dígitos $s = 3 + 1 + 9 = 13$ . Claramente, $13|13$ . Por lo tanto, $13|611$ lo cual es cierto ya que $611 = 13 \times 47$ .

Prueba:

La prueba de esta afirmación se escribe sola. Sea $a = (a_ma_{m-1} \ldots a_0)_{n+1}$ , donde $a_i$ son los dígitos de ' $a$ ' en la base ' $n+1$ '. $$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$$ Ahora bien, tenga en cuenta que \begin {align} n+1 & \equiv 1 \pmod n \\ (n+1)^k & \equiv 1 \pmod n \\ a_k \times (n+1)^k & \equiv a_k \pmod n \end {align} \begin {align} a & = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0 \\ & \equiv (a_m + a_{m-1} \cdots + a_0) \pmod n \\ a & \equiv s \pmod n \end {align} Por lo tanto, se ha demostrado.

Reclamación 2: La regla de divisibilidad de un número ' $a$ ' para ser dividido por ' $n$ ' es la siguiente. Expresar el número ' $a$ ' en la base ' $n-1$ '. Deja ' $s$ ' denotan la suma alternada de dígitos de ' $a$ ' expresado en base ' $n-1$ ', es decir, si $a = (a_ma_{m-1} \ldots a_0)_{n-1}$ , $s = a_0 - a_1 + a_2 - \cdots + (-1)^{m-1}a_{m-1} + (-1)^m a_m$ . Ahora $n|a$ si y sólo $n|s$ . De manera más general, $a \equiv s \pmod{n}$ .

Ejemplo:

Antes de ponernos a demostrarlo, veremos un ejemplo de ello. Digamos que queremos comprobar si $13|611$ . Expreso $611$ en la base $12$ . $$611 = 4 \times 12^2 + 2 \times 12^1 + B \times 12^0 = (42B)_{12}$$ donde $(42B)_{14}$ denota que el número decimal $611$ expresado en base $12$ , $A$ representa la décima cifra y $B$ representa el undécimo dígito. La suma alternada de los dígitos $s = B_{12} - 2 + 4 = 13$ . Claramente, $13|13$ . Por lo tanto, $13|611$ lo cual es cierto ya que $611 = 13 \times 47$ .

Prueba:

La prueba de esta afirmación se escribe sola como la anterior. Sea $a = (a_ma_{m-1} \ldots a_0)_{n+1}$ , donde $a_i$ son los dígitos de ' $a$ ' en la base ' $n-1$ '. $$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$$ Ahora bien, tenga en cuenta que \begin {align} n-1 & \equiv (-1) \pmod n \\ (n-1)^k & \equiv (-1)^k \pmod n \\ a_k \times (n-1)^k & \equiv (-1)^k a_k \pmod n \end {align} \begin {align} a & = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0 \\ & \equiv ((-1)^m a_m + (-1)^{m-1} a_{m-1} \cdots + a_0) \pmod n \\ a & \equiv s \pmod n \end {align} Por lo tanto, se ha demostrado.

Ventajas y desventajas:

La única ventaja obvia de las reglas de divisibilidad anteriores es que se trata de una regla de divisibilidad generalizada que puede aplicarse para cualquier ' $n$ '.

Sin embargo, la mayor desventaja de estas reglas de divisibilidad es que si un número está dado en el sistema decimal necesitamos expresar primero el número en una base diferente. Expresándolo en base $n-1$ o $n+1$ puede resultar más caro. (También podríamos intentar la división directa por $n$ en lugar de este procedimiento). Sin embargo, si el número dado ya está expresado en base $n+1$ o $n-1$ entonces la comprobación de la divisibilidad se convierte en una cuestión trivial.

Answer 2

La prueba de divisibilidad de base 10 por 11 tiene un análogo directo en otras bases. Por ejemplo, en base 12, 756899 es divisible por 13 porque 7+6+9 = 5+8+9. Se puede extender esto a un caso que no se da en base 10 porque 10+1 es primo: Si $n$ es cualquier factor de $b+1$ entonces se puede comprobar la divisibilidad mediante $n$ en la base $b$ formando las dos sumas de dígitos alternos y comprobando si difieren en un múltiplo de $n$ . Por ejemplo, considere la base 8. ¿Es el número ${7166}_8$ ¿divisible por 3? Lo es si y sólo si 7+6 y 1+6 difieren en un múltiplo de 3; obviamente, lo son, así que la respuesta es sí.

Las pruebas de divisibilidad por 2 y 5 tienen análogos en bases no primos. Por ejemplo, en base 12, los números son divisibles por 6 si y sólo si terminan en 0 o 6 ; divisibles por 4 si y sólo si terminan en 0 , 4 o 8 ; por 3 si y sólo si terminan en 0 , 3 , 6 o 9 y por 2 si y sólo si en 0 , 2 , 4 , 6 , 8 o A . Del mismo modo, la prueba de divisibilidad por 10 tiene un análogo obvio. En general, si $n$ divide $b$ entonces una base $b$ número $X$ es divisible por $n$ si y sólo si su último dígito es divisible por $n$ .

La prueba de divisibilidad por 3 tiene análogos en las bases $n$ donde $n-1$ no es primo; si $n-1$ es divisible por $k$ se puede comprobar la divisibilidad mediante $k$ sumando la base- $n$ dígitos y comprobar si la suma es divisible por $k$ . Por ejemplo, considere 82A en base 11. La suma de estos dígitos es 20, que es par, y también es un múltiplo de 5; tanto 2 como 5 dividen 11-1=10, por lo que 82A es un múltiplo de 5 y de 2. Pero la suma de los dígitos de 654 es 15, un múltiplo de 5 pero no de 2, por lo que 654 es un múltiplo de 5 pero no de 2.

Answer 3

Esta es una regla de divisibilidad para $d$ en la base $b$ , dado $d$ y $b$ son relativamente primos.

Dejemos que $k$ sea cualquier número entero tal que $kb\equiv 1 \pmod d$ . Entonces podemos tomar el último dígito del número que estamos probando, multiplicarlo por $k$ y sumarlo a los dígitos restantes, sin incluir el último dígito. Luego podemos repetir el proceso con el nuevo número formado. Obsérvese que todos los cálculos se hacen en base $b$ .

Por ejemplo, el para encontrar si un número, digamos $552839$ es divisible por 7 en base 10, podemos establecer $k=-2$ ya que $(-2)10=-20\equiv 1 \pmod 7$ . Entonces obtenemos la siguiente secuencia:

$$552839 \Rightarrow 55265 \Rightarrow 5516 \Rightarrow 539 \Rightarrow 35$$

Desde $35$ es divisible por 7, entonces el número original $552839$ también es divisible por 7.