¿Cómo funcionan las gráficas de divisibilidad?

Supongamos que desea hacer un gráfico de divisibilidad para$n$. Hacer$n$puntos y etiquetarlos$0, 1, \ldots n-1$.

Tendrá un "número actual" que cambiará a medida que avance por el gráfico. estarás en el punto$i$si el resto que obtienes al dividir el "número actual" por$n$es$i$. A medida que camina por el gráfico, el número actual cambiará y el punto cambiará para seguir el resto de dividir el nuevo número actual. Inicialmente, el "número actual" es$0$, entonces comienzas en el punto$0$.

Las flechas negras representan la operación de sumar 1 al número actual. Haz una flecha negra de cada punto$i$a$i+1$, y también de punto$n-1$marcar$0$.

Las flechas blancas representan la operación de multiplicar el número actual por 10. Haz una flecha blanca de cada punto$i$a$10\cdot i\bmod n$. es decir, desde$i$a lo que sea el resto es cuando divides$10\cdot i$por$n$. Por ejemplo, si$i$es 2 y$n$es 7, haces una flecha blanca del punto 2 al punto 6 porque el resto después de dividir$2\cdot10$por$7$es 6

Cualquier número actual se puede generar a partir de 0 sumando 1 y multiplicando por 10 en el orden correcto. Por ejemplo, para llegar a 213, comienzas en 0 y:

$$0\stackrel{+1}\to1\stackrel{+1}\to2 \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 rastrean el resto si agrega 1 al número actual y las flechas blancas rastrean lo que sucede con el resto si multiplica el número actual por 10.

A medida que recorre la gráfica, lleva un registro de cuál sería el resto en cada etapa si dividiera el número actual por$n$. Una vez que haya terminado de convertir el número actual en el número que desea verificar, el resultado es divisible por$n$solo si el resto fuera 0, es decir, solo si está de vuelta en el punto$0$donde empezaste.

Aquí hay un ejemplo, el gráfico correspondiente para$n=8$. Coloreé las flechas ×10 de azul en lugar de blanco, porque el azul es bonito:

Hice dos juegos de estos, para$2\le n\le 20$, que se pueden ver en línea ; disfrútalos y haz lo que quieras con ellos.

Pensé en agregar una nota a algunas de las respuestas anteriores.

Lo he redibujado con un diseño diferente. Es agradable porque muestra la simetría.

Las flechas negras, que corresponden a$+1$moverse alrededor del borde. Las flechas moradas corresponden a multiplicar por$10$. Los nodos se etiquetan con el resto después de la división por 7.

Pista: Los escalones negros añaden$1\pmod 7$y los escalones blancos se multiplican por$\,10\equiv 3\pmod 7.\,$Seguir la ruta evalúa el número en forma de Horner$\, ((\cdots d_n) 10 + \cdots + d_1) 10 + d_0.$Si trazas las flechas negras a partir del nodo blanco$\equiv 0\,$encontrará sucesivamente los nodos para$\,0,1,\ldots 6.\,$Entonces puedes verificar que las flechas blancas efectivamente se multiplican por$\,3\equiv 10\pmod 7.\,$Por ejemplo, el nodo$\equiv 1\,$hay un paso negro desde el nodo de inicio, y vemos que tomar un paso blanco desde$\,1\,$conduce al nodo que está a dos pasos negros de$\,1,\,$es decir, el nodo$\equiv 3,\,$Lo que significa que$\,10\cdot 1\equiv 3\pmod 7.\,$El gráfico es el de una máquina de estados finitos que evalúa el mod entero$7,\,$evaluando el polinomio radix en forma anidada de Horner.

Trabajemos con tu ejemplo,$\,325 = ((\color{#c00}3)10+\color{#0a0}2)10 + \color{blue}5,\ $entonces seguimos$\,\color{#c00}3\,$flechas negras para obtener$\,0\!+\! 1\! +\! 1\! +\! 1\equiv 3.\,$Luego seguimos una flecha blanca para obtener$\, (3)10 = 30.\,$Entonces$\,\color{#0a0}2\,$flechas negras para obtener$\,30+2 = 32\,$. Luego una flecha blanca para obtener$\,(32)10 = 320.\,$Entonces finalmente,$\,\color{blue}5\,$flechas negras para obtener$\,320+5 = 325,\,$donde se hacen todos los calculos mod$\,7\,$por la máquina

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

Esta es una representación de máquina de estado finito del número, similar a lo que obtendría si realizara una división larga pero ignorara el cociente hasta el momento. (Este en particular puede tener simplificaciones que oscurecen esa conexión).