Patrones en gráficos de división módulo$n$

Question

(He hecho una edición debido a los consejos de Alex Ravsky. Gracias a él).

General de la división de gráficos con los nodos de $1,2,\dots N$ y un borde entre el $n$ e $m$ cuando $n$ divide $m$ o $m$ divide $n$ son escasos y dar lugar a un interesante patrón visual.

A su vez, de la división de gráficos modulo $N$ con nodos $1,2,\dots N-1$ y un borde entre el $n$ e $m$ cuando $n|m$ modulo $N$ o $m|n$ modulo $N$, es decir, cuando existe un $k$ con $k\cdot n \equiv m \pmod{N}$ o viceversa, son densos. Especialmente cuando se $N$ es primo de la división gráfica modulo $N$ es isomorfo a la total $N-1$ gráfico.

Así que tiene sentido considerar la no-división de gráficos modulo $N$ con un borde entre el $n$ e $m$ cuando $n$ no divide $m$ o $m$ no divide $n$. (Tenga en cuenta que este no es el complemento de la división gráfica que tiene un borde entre el $n$ e $m$ cuando $n$ no divide $m$ e $m$ no divide $n$.) Estos gráficos son relativamente escasos, y especialmente isomorfo al vacío $N-1$ gráfico cuando se $N$ es primo.

Para la mayoría de los compuestos de números, estos gráficos no revelan nada interesante, por ejemplo, para $N=8$, $N=26$, e $N=90$:

Pero finalmente patrones interesantes surgen, por ejemplo, para $N=77$, $N=91$, e $N=121$:

La distinción de los patrones observados - nodos con un mayor grado que otros, visto como manchas oscuras, con líneas brillantes entre ellos es mayor cuando se $N$ es un producto de dos no demasiado pequeño de los números primos, por ejemplo, $77 = 7\cdot 11$, $91 = 7\cdot 13$, , $121= 11\cdot 11$.

Mis preguntas son:

1. ¿Cómo puede éste ser explicado?

2. ¿Cómo puede el específico de alto grado de los números se explica?

El alto grado de números para $N=77$ se $7, 11, 14,21,22, 21, 28, 33, 35,\dots$, en general los múltiplos de los factores primos de a$N$.

Answer 1

Es fácil comprobar que un número $n$ divide $m$ modulo $N$ fib $(N,n)|m$ fib $(N,n)|(N,m)$, donde $(N,n)$ (resp. $(N,m)$) es el máximo común divisor de los números de $N$ e $n$ (resp., $m$). Por lo tanto $n$ e $m$ son adyacentes en el gráfico iff no $(N,n)|(N,m)$ o no $(N,m)|(N,n)$, que es cuando se $(N,n)\ne (N,m)$. Por lo tanto, la gráfica es una completa $\tau(N)-1$-partita gráfica, donde $\tau(N)$ es el número de divisores del número de $N$, partes de la partición de la gráfica son indexados por los divisores de $N$ (que son menos de $N$), y una parte $[d]$ correspondiente a un divisor $d$ consiste de todos los números de $n$ entre $1$ e $N-1$ tal que $(N,n)=d$. Por ejemplo, para la gráfica de $N=8$ en la primera imagen debe ser $3$-partita de las piezas con $[1]=\{1,3,5,7\}$, $[2]=\{2,6\}$, e $[4]=\{4\}$. En particular, en la primera figura $1$ también tiene que ser adyacente a $2$, $4$, e $6$, debido a que no $(2|1)$, no $(4|1)$, e $(6|1)$. Desde un vértice de la gráfica es adyacente exactamente a vertises de todas las partes, sino por su propio, el conjunto de vértices de los grandes(st) grado son vértices de pequeño(est) de las piezas. Por ejemplo, para $N$ el mayor grado tiene un único vértice $N/2$ (ver las fotos de vértice $4$ para $N=8$, vértice $13$ para $N=26$, y el vértice $45$ para $N=90$); esto es así porque, por un divisor $n\ne N/2$ de $N$ parte $[n]$ contiene al menos dos vértices $n$ e $N-n$. En general, la parte $[d]$ consta de $\varphi(N/d)$ vértices, donde $\varphi$ es la función de Euler. Que es un vértice $n$ tiene un mayor grado de iff $\varphi(N/(N,n))$ es el más pequeño, que es el fib $ N/(N,n)$ es el menor divisor primo $p(N)$ de $N$. Hay $p(N)-1$ tales vértices $n$, es decir, los vértices $kN/p(N)$ con $k=1,\dots, p(N)-1$. Cuando $N=p_1p_2$ es un producto de dos números primos, a continuación, la gráfica es $3$-partita con piezas de $[1]$ de tamaño de $N-p_1-p_2+1$, $[p_1]$ de tamaño de $p_2-1$, e $[p_2]$ de tamaño de $p_1-1$. Por ejemplo, para $N=77$, $[7]=7,14,21,35,\dots, 70$ e $[11]=11,22,33,\dots, 66$, ver la cuarta y quinta fotos. Si $N=p^2$ para un primer número $p$ , a continuación el gráfico es $2$-partita, con la parte $[1]$ de tamaño de $[N-p]$, e $[p]$ de tamaño de $p-1$, ver la última imagen para $p=11$.