Dtyjlui

(I made an edit due to hints from Alex Ravsky. Thanks to him.)

General division graphs with nodes $1,2,dots N$ and an edge between $n$ and $m$ when $n$ divides $m$ or $m$ divides $n$ are sparse and give rise to one interesting visual pattern.

In turn, division graphs modulo $N$ with nodes $1,2,dots N-1$ and an edge between $n$ and $m$ when $n|m$ modulo $N$ or $m|n$ modulo $N$, i.e. when it exists a $k$ with $kcdot n equiv m pmod{N}$ or vice versa, are dense. Especially when $N$ is prime the division graph modulo $N$ is isomorphic to the complete $N-1$ graph.

So it makes sense to consider the non-division graphs modulo $N$ with an edge between $n$ and $m$ when $n$ doesn't divide $m$ or $m$ doesn't divide $n$. (Note that this is not the complement of the division graph which has an edge between $n$ and $m$ when $n$ doesn't divide $m$ and $m$ doesn't divide $n$.) These graphs are relatively sparse, and especially isomorphic to the empty $N-1$ graph when $N$ is prime.

For most composite numbers, these graphs don't reveal anything interesting, e.g. for $N=8$, $N=26$, and $N=90$:

But eventually interesting patterns emerge, e.g. for $N=77$, $N=91$, and $N=121$:

The distinctness of the observed patterns - nodes with a significantly higher degree than others, seen as dark spots with bright lines between them - is highest when $N$ is a product of two not too small primes, e.g. $77 = 7cdot 11$, $91 = 7cdot 13$, , $121= 11cdot 11$.

My questions are:

1. How can the latter be explained?




2. How can the specific high-degree numbers be explained?

The high-degree numbers for $N=77$ are $7, 11, 14,21,22, 21, 28, 33, 35,dots$, in general the multiples of the prime factors of $N$.

It is easy to check that a number $n$ divides $m$ modulo $N$ iff $(N,n)|m$ iff $(N,n)|(N,m)$, where $(N,n)$ (resp. $(N,m)$) is the greatest common divisor of the numbers $N$ and $n$ (resp., $m$). Thus $n$ and $m$ are adjacent in the graph iff not $(N,n)|(N,m)$ or not $(N,m)|(N,n)$, that is when $(N,n)ne (N,m)$. Thus the graph is a complete $tau(N)-1$-partite graph, where $tau(N)$ is the number of divisors of the number $N$, parts of the partition of the graph are indexed by divisors of $N$ (which are less than $N$), and a part $[d]$ corresponding to a divisor $d$ consists of all numbers $n$ between $1$ and $N-1$ such that $(N,n)=d$. For instance, for the graph for $N=8$ at the first picture should be $3$-partite with the parts $[1]={1,3,5,7}$, $[2]={2,6}$, and $[4]={4}$. In particular, in the first figure $1$ also has to be adjacent to $2$, $4$, and $6$, because not $(2|1)$, not $(4|1)$, and $(6|1)$. Since a vertex of the graph is adjacent exactly to vertises of all parts but its own, the set of vertices of large(st) degree are vertices from small(est) parts. For instance, for even $N$ the largest degree has a unique vertex $N/2$ (see the pictures for vertex $4$ for $N=8$, vertex $13$ for $N=26$, and vertex $45$ for $N=90$); this is so because for a divisor $nne N/2$ of $N$ part $[n]$ contains at least two vertices $n$ and $N-n$. In general, part $[d]$ consists of $varphi(N/d)$ vertices, where $varphi$ is Euler function. That is a vertex $n$ has a largest degree iff $varphi(N/(N,n))$ is the smallest, that is iff $ N/(N,n)$ is the smallest prime divisor $p(N)$ of $N$. There are $p(N)-1$ such vertices $n$, namely, vertices $kN/p(N)$ with $k=1,dots, p(N)-1$. When $N=p_1p_2$ is a product of two prime numbers then the graph is $3$-partite with parts $[1]$ of size $N-p_1-p_2+1$, $[p_1]$ of size $p_2-1$, and $[p_2]$ of size $p_1-1$. For instance, for $N=77$, $[7]=7,14,21,35,dots, 70$ and $[11]=11,22,33,dots, 66$, see the fourth and fifth pictures. If $N=p^2$ for a prime number $p$ then the graph is $2$-partite, with the part $[1]$ of size $[N-p]$, and $[p]$ of size $p-1$, see the last picture for $p=11$.