¿Cómo funciona la divisibilidad gráficos de trabajo?

Question

Me encontré con este método gráfico para comprobar la divisibilidad por $7$.

$\hskip1.5in$

Escriba un número $n$. Inicio en el pequeño blanco nodo en la parte inferior de la gráfica. Para cada dígito $d$$n$, siga $d$ flechas negras en un de la sucesión, y como usted se mueve de un dígito a la siguiente, siga $1$ flecha blanca).

Por ejemplo, si $n = 325$, siga $3$ flechas negras, entonces $1$ flecha blanca, a continuación, $2$ flechas negras, a continuación, $1$ (flecha blanca), y finalmente, $5$ flechas negras.

Si usted termina de vuelta en el blanco de nodo, $n$ es divisible por $7$.

Este método realmente funciona, me preguntaba por qué este trabajo y cómo podemos generar este tipo de gráfico para un entero arbitrario $k$?

Answer 1

Yo quisiera añadir una nota a algunas de las respuestas anteriores.

He vuelto a dibujar con un diseño diferente. Es bueno porque muestra la simetría.

Las flechas negras, que corresponden a $+1$ mueven alrededor del borde. La púrpura flechas corresponden a la multiplicación por $10$. Los nodos están etiquetados con el resto de la división por 7.

Answer 2

Supongamos que desea hacer una divisibilidad gráfico de $n$. Hacer $n$ puntos y con la etiqueta $0, 1, \ldots n-1$.

Usted tendrá un "número actual", que cambiará a medida que usted camina alrededor de la gráfica. Usted estará en el dot $i$ si el resto se obtiene de dividir el actual "número" por $n$$i$. Como usted camina alrededor de la gráfica, el número actual va a cambiar, y el punto va a cambiar para seguir el resto de dividir el nuevo número actual. Inicialmente, el "número" es $0$, por lo que se empieza en el punto a $0$.

Las flechas negras representan la operación de la adición de 1 al número actual. Hacer una flecha negra de cada punto $i$$i+1$, y también desde el punto de $n-1$ dot $0$.

Flechas blancas representan la operación de multiplicar el número por 10. Hacer una flecha blanca de cada punto $i$$10\cdot i\bmod n$. Es decir, de $i$ a lo que es el resto cuando se divide $10\cdot i$$n$. Por ejemplo, si $i$ 2 $n$ es de 7, se puede hacer una flecha blanca desde el punto 2 al punto 6, porque el resto después de dividir $2\cdot10$ $7$ es de 6.

Cualquier número puede ser generado a partir de 0 mediante la adición de 1 y se multiplica por 10 en el orden correcto. Por ejemplo, para llegar a 213, que empiezan en 0 y:

$$ 0\stackrel{+1}\1\stackrel{+1}\-2 \stackrel{\times10}\to20\stackrel{+1}\to21 \stackrel{\times10}\to210\stackrel{+1}\to211\stackrel{+1}\to212\stackrel{+1}\to213$$

Comenzando en el punto 0 y siguiendo las flechas le da, en cada etapa, el resultado de dividir el número actual por $n$. Las flechas negras de la pista el resto si que sumar 1 al número actual, y las flechas blancas de la pista de lo que sucede con el resto si se multiplica el número por 10.

A medida que atraviesan el gráfico, usted está guardando la pista de lo que el resto sería en cada etapa, si se divide el número actual por $n$. Después de que haya terminado la construcción de la actual número en el número que desea comprobar, el resultado es divisible por $n$ sólo si el resto sería 0, es decir, sólo si estás de vuelta en el dot $0$ donde se inició.

He aquí un ejemplo, la gráfica correspondiente para $n=8$. He coloreado con el ×10 flechas de color azul en vez de blanco, porque el azul es bonito:

He hecho dos juegos de estos, para $2\le n\le 20$, que se pueden ver en línea; por favor, disfrutar de ellos y hacer lo que quieras con ellas.

Answer 3

Sugerencia: El negro pasos agregar $1\pmod 7$, y el blanco de los pasos multiplicar por $\,10\equiv 3\pmod 7.\,$ Siguiendo la ruta que se evalúa el número de Horner forma $\, ((\cdots d_n) 10 + \cdots + d_1) 10 + d_0.$ Si usted traza las flechas negras a partir de la blanca nodo $\equiv 0\,$ te sucesivamente encontrar los nodos para $\,0,1,\ldots 6.\,$ a Continuación, puede comprobar que las flechas blancas de hecho multiplicar por $\,3\equiv 10\pmod 7.\,$ Por ejemplo, el nodo $\equiv 1\,$ es uno negro paso desde el nodo de inicio, y vemos que tomar una blanca paso de $\,1\,$ conduce al nodo que es negro dos pasos de $\,1,\,$ i.e el nodo $\equiv 3,\,$, lo que significa que $\,10\cdot 1\equiv 3\pmod 7.\,$ La gráfica es la de una máquina de estados finitos que evalúa el entero mod $7,\,$ mediante la evaluación de la base polinomio en anidados Horner forma.

Vamos a trabajar fuera de su ejemplo, $\,325 = ((\color{#c00}3)10+\color{#0a0}2)10 + \color{blue}5,\ $, por lo que seguimos $\,\color{#c00}3\,$ flechas negras para conseguir $\,0\!+\! 1\! +\! 1\! +\! 1\equiv 3.\,$, Luego le sigue una flecha blanca para conseguir $\, (3)10 = 30.\,$ $\,\color{#0a0}2\,$ flechas negras para conseguir $\,30+2 = 32\,$. A continuación, una flecha blanca para conseguir $\,(32)10 = 320.\,$, Entonces, finalmente, $\,\color{blue}5\,$ flechas negras para conseguir $\,320+5 = 325,\,$ donde todos los cálculos se hacen mod $\,7\,$ por la máquina.

Answer 4

Sí, usted puede encontrar gráficos para la divisibilidad por cualquier número en cualquier base.

Esta es una máquina de estados finitos representación del número, similar a lo que se obtendría si se realiza la división larga, pero se omite el cociente hasta ahora. (Este en particular puede tener simplificaciones que oscuro que la conexión).