# Patterns in division graphs modulo $n$

(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 $$k\cdot 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 = 7\cdot 11$$, $$91 = 7\cdot 13$$, , $$121= 11\cdot 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$$.

• Why is there no edge between $1$ and the even numbers in the graph for $N=8$? While $1$ divides all of them, it is not divisible by any them, or is it? – Peter Košinár Jan 17 at 19:52

## 1 Answer

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,3,5,7\}$$, $$=\{2,6\}$$, and $$=\{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 $$n\ne 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 $$$$ 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,14,21,35,\dots, 70$$ and $$=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 $$$$ of size $$[N-p]$$, and $$[p]$$ of size $$p-1$$, see the last picture for $$p=11$$.

• The graphs are defined as symmetric (undirected) graphs, right. I wanted to make this clear by saying "draw a line between $n$ and $m$" instead of "draw an arrow from $n$ to $m$". The full definition so would have to be: $n$ and $m$ are related when $n|m$ modulo $N$ or $m|n$ modulo $N$. – Hans-Peter Stricker Jan 16 at 8:28
• @HansStricker OK, but then in a complement of a division graph modulo $N$ there is an edge between $n$ and $m$ iff $n$ does not divide $m$ modulo $N$ and $n$ does not divide $m$ modulo $N$. In particular, the graph at the first picture is not complement of a division graph, because it has an edge between $3$ and $6$, whereas $3$ divides $6$, right? – Alex Ravsky Jan 16 at 9:35
• You are right. I have to think about it, maybe I made a wrong argument. – Hans-Peter Stricker Jan 16 at 9:40
• The graphs I'm talking about are not the complements of division graphs: There's not an edge between $n$ and $m$ when neither $n|m$ nor $m|n$ (modulo $N$ omitted), i.e. NOT($n|m$ OR $m|n$) = NOT($n|m$) AND NOT($m|n$), but when NOT($n|m$) OR NOT($m|n$). Of course this makes a huge difference conceptually, thanks for pointing this out! So you don't get the "complement" by just swapping edges and non-edges, but you have to calculate it from sratch. (Should I edit my question, what do you suggest?) – Hans-Peter Stricker Jan 16 at 10:13
• Done. Do you find it OK? – Hans-Peter Stricker Jan 16 at 10:49