Divisibility Graphs and Modular Multiplication Tables

Abstract

Consider the graph with the residue classes modulo n as vertices, and the following edges: “additive” edges from a to a + 1; “multiplicative” edges from a to ab for some fixed b. This graph illustrates a criterion for divisibility by n for numbers written in base b. By varying n and b, we see a great variety of structures: this topic connects arithmetic to graph theory and has the beauty of string art. For divisibility graphs we investigate the existence of triangles and other cycles, the girth, the minimum/maximum of the vertex degree, the chromatic number, and the planarity.

MSC:

• 05C90
• 11A07

1 Introduction

It is natural to display the residue classes modulo n as the vertices of a regular n-gon in cyclic order. Thus adding 1 to a residue lets us move to the next residue along a side of the n-gon, while multiplying by some integer b lets us usually move along a diagonal of the n-gon (occasionally we move along a side or we do not move at all). The divisibility graph $D_{n,b}$, which is the object of our investigation, is the graph defined as follows: its vertices are the vertices of the regular n-gon; the “additive” edges are the oriented sides from a to a + 1; the “multiplicative” edges go from a to ba and are usually diagonals (occasionally they can be a loop or a side). Our goal is to study the family of divisibility graphs $D_{n,b}$ by varying n and b: as expected, the graph properties depend on the arithmetic properties of the pair n, b. We also consider the corresponding simplified graphs $D{\prime }_{n,b}$, where double edges and loops are removed and edge orientation is neglected. For divisibility graphs, we investigate the existence of cycles (triangles and rectangles in the canonical representation), the girth, the minimum/maximum vertex degree, the chromatic number, and planarity. See Section 2 for a summary of our results.

One motivation for considering the graph $D_{n,b}$ is that, for $b\ge 2$, it illustrates a divisibility criterion for an integer to be divisible by n that makes use of the digits in base b, see Remark 2. It seems that divisibility graphs were introduced by David Wilson in 2009 to illustrate the divisibility criterion for n = 7 in base b = 10, according to Tanya Khovanova [4]. Another motivation for studying these graphs is that they connect graph theory with arithmetic in a fascinating way, and they are beautiful objects with a great variety of structures by varying n and b, see, for example, Figures 1–3.

Fig. 1 $D{\prime }_{125,51}$.

Fig. 2 $D{\prime }_{200,99}$.

Fig. 3 $D{\prime }_{500,322}$.

Considering only the multiplicative edges of $D{\prime }_{n,b}$, one obtains the graph of modular multiplication by b, which has previously been considered to popularize mathematics. These other graphs are optically similar, as to obtain back $D{\prime }_{n,b}$ one only needs to include all sides of the n-gon. Nevertheless, the graph structures are very different: for example, having the additive edges ensures the existence of cycles. These other graphs are not our object of study, so we refer the reader to the book by Daniel Shanks [9] and to online resources like [6, 7]. In particular, these works provide a geometrical explanation for the $(b-1)$-foil pattern that will also be seen in our divisibility graphs, see Figures 4–6. Let us also mention the existence of websites like [5] which show the graph of modular multiplication by b, all based on the parameters n and b entered by the user.

Fig. 4 $D{\prime }_{125,3}$.

Fig. 5 $D{\prime }_{125,4}$.

Fig. 6 $D{\prime }_{125,5}$.

There is still a great deal to explore about divisibility graphs, and this work seems to offer the first deep investigation on the subject. Beyond our conjectures, some of our results can be improved upon, and there are surely features of divisibility graphs that we have not yet considered. We hope that some of our readers will embrace this challenge. Moreover, we hope that many readers introduce divisibility graphs to a wider audience, because it is an accessible topic (related to known divisibility criteria) that connects arithmetic to graph theory and that possesses the beauty of string art.

2 Mathematical Overview

Definition 1.

Given two integers n, b with $n\ge 1$, the divisibility graph $D_{n,b}$ is the directed multigraph with vertices $(a\mathrm{mod}n)$ for $0\le a<n$ and with the following edges: additive edges from $(a\mathrm{mod}n)$ to $(a+1\mathrm{mod}n)$; multiplicative edges from $(a\mathrm{mod}n)$ to $(\mathit{abmodn})$. The simplified divisibility graph $D{\prime }_{n,b}$ is obtained from $D_{n,b}$ by neglecting edge directions and by removing loops and double edges.

We canonically represent the vertices of a divisibility graph as the vertices of a regular polygon in cyclic order, see for example Figure 7.

Fig. 7 $D_{7,3}$.

Fig. 8 $D{\prime }_{11,6}$.

Replacing b by its remainder modulo n does not affect the divisibility graph. Thus, to avoid trivial cases, we will assume that $n\ge 3$ and $1<b<n$. Moreover, we shall denote a vertex by any integer in the given residue class modulo n.

Remark 2.

The divisibility graph $D_{n,b}$ provides a divisibility criterion by n considering the digits of a number expressed in base b. This is because the number $c_k{b}^k+\cdots +c_1{b}^1+c_0{b}^0$ (with $k,c_0,\dots ,c_k\ge 0$) corresponds to the end vertex of the following walk in $D_{n,b}$: start at 0; for $i=k,\dots ,0$, take c_i additive edges and in case i > 0, take one more multiplicative edge. This assertion can be proven by induction on k: the base case k = 0 is obvious; for the induction step, write the given number as $ba+c_0$ with $a=c_k{b}^{k-1}+\cdots +c_1{b}^0$, and complete the known walk for a by taking one multiplicative edge and c₀ additive edges.

For example, $21=2·3^2+1·3^1+0·3^0$ is divisible by 7 because in $D_{7,3}$ we walk from 0 to 0 by taking two additive edges, one multiplicative edge, one additive edge, and once more a multiplicative edge, see Figure 7.

To ease notation, we call d the greatest common divisor of n and b, we understand that congruences are modulo n (unless specified otherwise), we call an integer a unit if its residue class modulo n is a unit, and we say that two edges overlap if, neglecting their orientation, they coincide. We now recall some notions from graph theory (for references, see for example [1, 3]).

Definition 3.

Let G be an undirected graph. A triangle in G is a cycle of length 3. The girth of G is the length of a smallest cycle. The vertex degree $\mathrm{deg}(a)$ for a vertex a of G is the number of incident edges. We denote by $\delta (G)$ (respectively, $\Delta (G)$) the minimum (respectively, maximum) degree, namely the minimum (respectively, maximum) among all vertex degrees. The chromatic number of G, denoted by $\chi (G)$, is the smallest positive integer k such that G admits a k-coloring, namely a map from the vertex set to $\{0,\dots ,k-1\}$ such that any two adjacent vertices have distinct images. The graph G is called planar if it can be drawn on the plane without crossing edges.

Our main results are the following assertions:

Main Theorem. For simplified divisibility graphs, the following hold:

1. The graph $D{\prime }_{n,b}$ contains a triangle for every b if and only if n = 4, n is prime, or n is a power of 3.

2. There is a rectangle in the canonical representation of $D{\prime }_{n,b}$ for some value $1<b<n$ if and only if n = 4 or $n\equiv 0,\pm 2,\pm 6\mathrm{mod}16$.

3. The girth of $D{\prime }_{n,b}$ is at most 7. It is at most 5 if $b^2\cancel{\equiv }1$, and at most 4 if $b^2\equiv b$. The girth equals 3 if b–1 is a unit or $b=n-1$ or $b^2\equiv 0$.

4. We have $\delta (D{\prime }_{n,b})\in \{2,3\}$ and $\Delta (D{\prime }_{n,b})\in \{d+1,d+2,d+3\}$. Moreover, we have $\delta (D{\prime }_{n,b})=2$ if and only if b or b–1 is a unit. Further, all vertex degrees in $D{\prime }_{n,b}$ lie in $\{2,3,d+1,d+2,d+3\}$.

5. We have $\chi (D{\prime }_{n,b})\le 4$. Further, $\chi (D{\prime }_{n,b})=2$ holds if and only if $n\equiv 2\mathrm{mod}4$ and $b=\frac{n}{2}+1$.

The outline of the paper is as follows: after some preliminary results in Section 3, we consider cycles in $D{\prime }_{n,b}$ in Section 4 and the vertex degree in Section 5. Finally, in Sections 6 and 7, we respectively consider the chromatic number of $D{\prime }_{n,b}$ and investigate whether $D{\prime }_{n,b}$ is planar. In particular, we provide evidence for the following two conjectures:

Conjecture 4. We have $\chi (D{\prime }_{n,b})\le 3$.

Conjecture 5. For $n\ge 13$ odd, $D{\prime }_{n,b}$ is planar if and only if $b=n-1$. For $n\ge 16$ even, $D{\prime }_{n,b}$ is planar if and only if $b\in \{\frac{n}{2}-1,\frac{n}{2},n-1\}$.

3 Preliminaries

We begin with some general observations. For a prime number p, the p-adic valuation of a nonzero integer k is the biggest exponent $v_p(k)$ of p dividing k.

Remark 6.

The simplified divisibility graph $D{\prime }_{n,b}$ (with the additive edges forming a regular n-gon) is symmetric with respect to the line connecting 0 to the center of the n-gon. Indeed, the symmetry maps the n-gon to itself, and it maps the multiplicative edge (a, ba) to the edge $(n-a,b(n-a))$.

Moreover, $D{\prime }_{n,b}$ passes through the center of the n-gon if and only if for the 2-adic valuation we have $v_2(b-1)<v_2(n)$. Indeed, we precisely need the congruence $bx\equiv x+\frac{n}{2}$ to be solvable. Notice that in $D{\prime }_{125,51}$ (see Figure 1) the multiplicative edges do not connect vertices that are almost opposite.

Remark 7.

Consider the divisibility graph $D_{n,b}$ and some vertex a. The outgoing multiplicative edge at a is a loop if and only if $(b-1)a\equiv 0$, thus we have a loop at 0, and this is the only loop if and only if b–1 is a unit. The outgoing multiplicative edge at a can overlap an additive edge: this happens if and only if $(b-1)a\equiv \pm 1$, so it happens only if b–1 is a unit and in this case there is precisely one multiplicative edge that equals an additive edge (respectively, the reverse of an additive edge), namely the edge $({(b-1)}^{-1},{(b-1)}^{-1}+1)$ (respectively, the edge $(-{(b-1)}^{-1},-{(b-1)}^{-1}-1)$).

Remark 8.

A vertex in $D_{n,b}$ has no incoming multiplicative edge unless it is a multiple of d (as n and b are multiples of d), and in this case it has precisely d incoming multiplicative edges (a solution for $bx\equiv d$ being given by Bézout’s identity).

Consider the multiplication by b on the residue classes modulo n, represented by the multiplicative edges of $D_{n,b}$. Notice that all vertices are preperiodic under iterates of this map. Moreover, a vertex a is periodic if and only if we have $\gcd (ba,n)=\gcd (a,n)$, hence all vertices are periodic if and only if b is a unit.

Notice that the vertices a with the property $\gcd (ba,n)=\gcd (a,n)$ are precisely the multiples of g, where g is the largest integer of the form $\gcd (b^x,n)$ for some positive integer x, so that for every prime number p, the p-adic valuation $v_p(g)$ equals $v_p(n)$ if p divides b, and it is 0 otherwise. Then we are claiming that the periodic vertices are precisely the multiples of g. For example, if n is even, then $\frac{n}{2}$ is periodic if and only if b is odd.

A periodic vertex a must be a multiple of g because the quantity $\gcd (b^{x}a,n)$ does not decrease by increasing x and thus it is constant if a is periodic. Conversely, if $a:=a\prime g$ is a multiple of g, then the congruence $(b^x-1)a\prime \equiv 0\mathrm{mod}\frac{n}{g}$ is solvable (because b is a unit modulo $\frac{n}{g}$), hence the congruence $(b^x-1)a\equiv 0$ is solvable and a is periodic.

If G is a graph, then a minor of G is a graph that can be obtained from G by deletion and contraction of edges, as well as deletion of some isolated vertices. Given a subset of the vertices of G, the induced subgraph has precisely those vertices, and it has as edges all edges of G between them.

Remark 9.

If m > 1 is a divisor of n, then $D_{n/m,b}$ is a minor of $D_{n,b}$. Indeed, by contracting the edges between multiples of m we obtain a graph with n/m vertices such that $D_{n/m,b}$ is a subgraph (notice that $bk\equiv k\prime$ mod $\frac{n}{m}$ implies $\mathit{bkm}\equiv k\prime m$ for all integers $k,k\prime$).

Remark 10.

The subgraph $D_{n,b}^{\times }$ of $D_{n,b}$ obtained by removing the additive edges is the union of orbits for the multiplication by b. A periodic orbit is a cycle (possibly consisting of one or two vertices). Two orbits are either disjoint or have their periodic cycle in common. A connected component of $D_{n,b}^{\times }$ is as follows: there is one periodic cycle and attached to each vertex of the cycle there are d–1 vertices outside the cycle (one incoming multiplicative edge belongs to the cycle). Each of the above vertices outside the cycle is the root of a d-ary tree: these trees are pairwise disjoint and do not intersect the cycle.

Remark 11.

If m > 1 is a divisor of n, then we define G_m as the induced subgraph on the vertices of $D{\prime }_{n,b}$ that are multiples of m. Thus G_m can be obtained from $D_{n/m,b}$ (identifying multiples of m modulo n and residue classes modulo n/m) by removing additive edges and loops, and neglecting edge directions. Moreover, G_m can be obtained from $D_{n,b}^{\times }$ as the induced subgraph on the multiples of m, removing loops and neglecting edge directions (for m = d, the induced subgraph only loses leaves with respect to $D_{n,b}^{\times }$). An example for G_d can be found in Figure 12.

4 Cycles

To study cycles, we first classify triangles in $D{\prime }_{n,b}$ according to the number of additive edges:

Table

# additive edges	vertices (must be distinct)	further conditions
3	0, 1, 2	n = 3
2	$a,a+1,a+2$	$ab\equiv a+2$ or $(a+2)b\equiv a$
1	$a,a+1,ab$	$a{b}^2\equiv a+1$
1	$a,a+1,(a+1)b$	$(a+1)b^2\equiv a$
0	$a,ab,a{b}^2$	$a{b}^3\equiv a$

Lemma 12.

Let n be a positive, composite, odd integer and let p > 3 be a prime factor of n. Then there exists a positive integer $x<\frac{n}{p}$ such that $p^2{x}^2+3px+3$ is coprime to n.

Proof.

If n is a power of p we can take $x:=1$, while if n is a multiple of 3 we can take $x:=\frac{n}{3^{v_3(n)}p}$ because n has no prime factor in common with $$p^2{x}^2+3px+3=\frac{n^2}{3^{2v_3(n)}}+3\frac{n}{3^{v_3(n)}}+3 .$$

Finally, if n is coprime to 3 and it has a prime factor q > 3 different from p, we may take $x:=\frac{tn}{p{q}^{v_q(n)}}$ for some integer $0<t<q$. Indeed, n and $p^2{x}^2+3px+3$ can have at most the prime factor q in common and, for some choice of t, the latter integer is not divisible by q: that polynomial in x has at most two roots modulo q, and different choices for t give different values of x modulo q. □

Proof

of Main Theorem 1. For the “if” implication, we can check by hand the case n = 4 and the above classification allows us to deal with $n\ge 5$ prime. Now suppose that n is a power of 3 and write $k:=v_3(n)$ and $v:=v_3(b-1)$. If v = 0, we may resort to the above classification, so suppose v > 0. Notice that $a:=3^{k-v-1}$ is an integer and $a(b^3-1)\equiv 0$. So the vertices a, ab, ab² form a triangle, as they are pairwise distinct: $a\cancel{\equiv }ab$ because $3^{k-v-1}(b-1)\cancel{\equiv }0$; $a\cancel{\equiv }a{b}^2$, else $ab\equiv a{b}^3\equiv a$; one similarly argues that $ab\cancel{\equiv }a{b}^2$.

For the “only if” implication, assume that $n\ne 4$ is neither prime, nor a power of 3. If n is even and $b=\frac{n}{2}+1$, then $D{\prime }_{n,b}$ contains no triangle because ab is congruent to a or $a+\frac{n}{2}$. Now suppose that n is odd, take p and x as in Lemma 12 and set $b:=px+1$. There is no triangle in $D{\prime }_{n,b}$ with additive edges because, for instance, $ab\equiv a+2$ implies $\mathit{apx}\equiv 2$; this is impossible because 2 is a unit and p divides n. We also exclude triangles with zero additive edges because $a{b}^3\equiv a$ means $\mathit{apx}(p^2{x}^2+3px+3)\equiv 0$, implying $\mathit{apx}\equiv 0$ and hence $ab\equiv a(px+1)\equiv a$. □

Figures 10 and 11 show that the girth of $D{\prime }_{n,b}$ can be as large as 7. It can, however, not be greater:

Proof

of Main Theorem 3. By the above classification, $D{\prime }_{n,b}$ contains a triangle whenever b–1 is a unit, so we may exclude this case. For $b=n-1$ or $b^2\equiv 0$ we have the triangle $(0,1,b)$. For $b^2\equiv 1$, we have the following cycle in $D{\prime }_{n,b}$ (in case two vertices are the same, we take a shorter cycle): $$0\to 1\to b\leftarrow (b-1)\stackrel{·b}{\leftarrow }(1-b)\leftarrow (-b)\leftarrow (-1)\to 0 .$$

For $b^2\equiv b$, we have the cycle $(0,1,b,b-1)$. For b not a unit, there is an integer $a\cancel{\equiv }0,1,-1$ such that we have the cycle $(0,1,b,a+1,a)$ (if $b\equiv a+1$, we take a cycle of length 4 instead). For b a unit such that $b^2\cancel{\equiv }1$, calling a its inverse, we consider the following cycle: $$1\to b\to (b+1)\stackrel{·b}{\leftarrow }(a+1)\leftarrow a\stackrel{·b}{\to }1 .$$

It is of length 5. □

Remark 13.

Consider those triangles inside $D{\prime }_{n,b}$ that are equilateral triangles in the canonical representation, as in Figure 9. For n > 3 there is such a triangle based at some vertex a if and only if n is divisible by 3 and the three numbers $(b-1)a,(b-1)ba,(b-1)b^{2}a$ are congruent to $\frac{n}{3}$. So we must have $(b-1)a\equiv \frac{n}{3}$ and $b\equiv 1\mathrm{mod}3$. We deduce that there is an equilateral triangle if and only if n = 3 or $1\le v_3(b-1)\le v_3(n)-1$. Similarly, to find a regular k-gon inside the canonical representation of $D{\prime }_{n,b}$ (beyond n = k) it is necessary and sufficient that for any prime divisor p of k we have $v_p(k)\le v_p(b-1)\le v_p(n)-v_p(k)$.

Fig. 9 $D{\prime }_{81,19}$.

Fig. 10 $D{\prime }_{21,8}$ has girth 7.

Fig. 11 $D{\prime }_{56,43}$ has girth 7.

Fig. 12 G₂ for $D_{52,10}$.

Fig. 13 A rectangle with four multiplicative edges in $D{\prime }_{64,3}$.

Now we turn our attention to rectangles in the canonical representation of simplified divisibility graphs. For example $D{\prime }_{64,3}$ contains a rectangle built with sides and diagonals of a regular octagon. Observe that a 4-cycle $(x,y,z,w)$ in $D{\prime }_{n,b}$ forms a rectangle if and only if $x-z\equiv y-w\equiv \frac{n}{2}$ (i.e., there are two pairs of diametrically opposite vertices). In particular, there is no rectangle in $D{\prime }_{n,b}$ if n is odd hence we will suppose that n is even.

Remark 14.

We present a modification of the criterion due to Neeyanth Kopparapu in [11] to have a rectangle of the form $(a,ba,b^{2}a,b^{3}a)$ for some vertex a that is a unit. In short, we must have $b^4-1\equiv 0$ and $v_2(b^2-1)<v_2(n)$ (in particular, $n\equiv 0\mathrm{mod}16$ and $\phi (n)\equiv 0\mathrm{mod}8$). See Remark 16 for a more general criterion for the existence of a k-cycle $(a,ba,\dots ,b^{k-1}a)$ in $D{\prime }_{n,b}$.

Having all additive edges in a rectangle is only possible for n = 4. If n > 4 is even, then there is no rectangle in $D{\prime }_{n,b}$ containing an edge which is both additive and multiplicative. Indeed, assume otherwise that a rectangle in $D{\prime }_{n,b}$ contains the edge $(a,a\pm 1)$ which is both additive and multiplicative. As n is even, a must be odd and b must be even. We can write the rectangle as $(a,a\pm 1,a+\frac{n}{2},a\pm 1+\frac{n}{2})$. Since $n\ge 6$, a and $a\pm 1+\frac{n}{2}$ are not consecutive modulo n, and thus $(a\pm 1+\frac{n}{2},a)$ must be a multiplicative edge, contradicting the parity of a and b. It thus follows that if there are any additive edges in a rectangle of $D{\prime }_{n,b}$, then two of its edges are additive and two of them are multiplicative. This is treated in the following:

Remark 15.

We classify the rectangles with precisely two edges that are not multiplicative (they must be opposite). If the two multiplicative edges have the same orientation, then the rectangle is without loss of generality of the form $(bx,x,x+1,bx-1)$ with $b(x+1)\equiv bx-1$ and $x-bx+1\equiv \frac{n}{2}$, which means $b=n-1$ and $2x+1\equiv \frac{n}{2}$. In particular, $n\equiv 2\mathrm{mod}4$ and we may take $x=\frac{n-2}{4}$. Now suppose that the two parallel edges have opposite orientation, and let $(x,x+1)$ be an additive edge. If the multiplicative edge is incoming at x, the vertices are $(bx,x,x+1,bx-1)$. We have $b(bx-1)\equiv x+1$ and $bx-1-x\equiv \frac{n}{2}$. Else, the vertices are $(x,x+1,bx+b,bx+b+1)$ and we have $b(bx+b+1)\equiv x$ and $bx+b-x\equiv \frac{n}{2}$. Notice that $D{\prime }_{n,b}$ either contains rectangles of both cases, or of none: given a rectangle of one case, one obtains a rectangle of the other case by replacing its vertices by their opposites modulo n.

Proof

of Main Theorem 2. Clearly there is no rectangle for n = 3, while the additive edges form a square for n = 4. Now suppose that $n\ge 5$ is even. By Remark 15 there is a rectangle in $D_{n,n-1}$ if $\frac{n}{2}$ is odd. Moreover, if $n\equiv 0\mathrm{mod}16$, then $D{\prime }_{n,3}$ contains the rectangle $(x,3x,9x,27x)$ where $x=\frac{n}{16}$. To conclude we have to prove that there is no rectangle if $n\equiv \pm 4,8\mathrm{mod}16$.

If $D{\prime }_{n,b}$ contains a rectangle of the form $(x,bx,b^{2}x,b^{3}x)$, then we must have $x(b^2-1)\equiv \frac{n}{2}\equiv x(b^3-b)$, so that $b\frac{n}{2}\equiv \frac{n}{2}$, hence $\frac{n}{2}(b-1)\equiv 0$ and b must be odd. Since $x(b^2-1)\equiv \frac{n}{2}$ and $b^2-1$ is a multiple of 8, also $\frac{n}{2}$ is a multiple of 8 and hence $n\equiv 0\mathrm{mod}16$.

If $D{\prime }_{n,b}$ contains a rectangle with two multiplicative edges of the same direction, it holds that $n\equiv 2\mathrm{mod}4$ and thus $n\cancel{\equiv }\pm 4,8\mathrm{mod}16$.

By Remark 15, the only remaining case to consider is $D{\prime }_{n,b}$ containing a rectangle of the form $(bx,x,x+1,bx-1)$. We prove that $n\cancel{\equiv }0\mathrm{mod}4$ by contradiction. Write $n=4k$. Now $b(bx-1)\equiv x+1$ and $bx-1-x\equiv \frac{n}{2}$ imply $b(bx-1)\equiv x+1\equiv \frac{n}{2}+bx$, so that $b\frac{n}{2}\equiv b(bx-x-1)\equiv b^{2}x-bx-b\equiv \frac{n}{2}$ and $2k(b-1)$ is a multiple of 4k, meaning b is odd. But $bx-1-x\equiv \frac{n}{2}$ gives $x(b-1)-2k-1\equiv 0$, whose left member is odd, a contradiction. □

We conclude this section with two remarks on k-cycles:

Remark 16.

Let $k\ge 3$. In [10] Hans-Peter Stricker gives a criterion to have a k-cycle of the form $(a,ba,b^{2}a,b^{3}a,\dots ,b^{k-1}a)$ for some vertex a. Replace n by $m:=\frac{n}{\gcd (n,a)}$ and hence suppose that a is a unit. Then we precisely need that b is a unit with multiplicative order k. So the general criterion becomes that there exists a divisor m of n such that $(b\mathrm{mod}m)$ is a unit with multiplicative order k.

Remark 17.

Let $k\ge 3$. Assume that $n\ge k$ and that b–1 is a unit. Then there exists a k-cycle: for example, the vertices $(a,a+1,\dots ,a+k-1)$ where $a:={(b-1)}^{-1}(k-1)$ form a k-cycle because we have $ba\equiv a+k-1$.

5 Vertex Degree

An oriented graph is Eulerian if and only if there are the same number of outgoing and incoming edges at each vertex.

Remark 18.

The graph $D_{n,b}$ is Eulerian if and only if b is a unit. Indeed, if b is a unit, then there is precisely one incoming multiplicative edge at every vertex. If b is not a unit, then there is no incoming multiplicative edge at 1.

Remark 19.

The vertex degree is at most 3 for vertices that are not multiples of d by Remark 8. Moreover, by Remark 7, for $d\ge 1$ no additive edge at 0 overlaps a multiplicative edge. Thus the vertex degree at 0 is d + 1 (the outgoing multiplicative edge is a loop).

Proof

of Main Theorem 4. Recall Remark 7. If b is a unit (respectively, b is not a unit and b–1 is a unit), then 0 (respectively, the multiplicative inverse of b–1) has vertex degree 2. Now suppose that b and b–1 are not units: no multiplicative edge overlaps an additive edge; we have $\delta (D{\prime }_{n,b})\ge 3$ because, if the outgoing multiplicative edge is a loop, then there is an incoming multiplicative edge that is not a loop ($ba\equiv a$ implies $b(a+c)\equiv a$ for any $c\cancel{\equiv }0$ such that $bc\equiv 0$).

We have $\Delta (D{\prime }_{n,b})\le d+3$ because at every vertex there are at most d incoming multiplicative edges; we show that the vertex degree of b is at least d + 1. For $0\le i<d$, the d incoming multiplicative edges $(1+i\frac{n}{d},b)$ are distinct; if one of them is a loop, they do not overlap additive edges ($b^2\equiv b$ implies $b\cancel{\equiv }b(b\pm 1)$). Assume both additive edges at b overlap incoming multiplicative edges. Then $b(b+1)\equiv b\equiv b(b-1)$, in particular implying that $b^2\equiv 0$. The outgoing multiplicative edge at b thus ends at 0 and is not equal to any incoming multiplicative edge at b. Therefore the vertex degree at b is at least d + 1 in all cases.

Finally, suppose that a is a vertex. If d does not divide a, then $\mathrm{deg}(a)\in \{2,3\}$ by Remark 19. If d does divide a, then $d+1\le \mathrm{deg}(a)\le d+3$ by the above argument given for a = b. □

Remark 20.

An integer $n\ge 3$ is a prime power if and only if for all b we have $\delta (D{\prime }_{n,b})=2$. Indeed, by Main Theorem 4 the latter condition means that, for every integer a, at least one of a and a–1 is a unit (if n had distinct prime factors p, q, then the congruences $a\equiv 0\mathrm{mod}p$ and $a\equiv 1\mathrm{mod}q$ have a common solution).

Figures 15–17 are examples for the three cases in the following result:

Fig. 14 A rectangle with two multiplicative edges in $D{\prime }_{62,5}$.

Fig. 15 $D{\prime }_{10,3}$ has maximum degree d + 3.

Fig. 16 $D{\prime }_{10,4}$ has maximum degree d + 2.

Fig. 17 $D{\prime }_{10,5}$ has maximum degree d + 1.

Theorem 21.

If b–1 is not a unit, then we have $$\Delta (D{\prime }_{n,b})=\{\begin{array}{cc}d+1\hfill & \text{if }bd\equiv d\hfill \\ d+2\hfill & \text{if }bd\cancel{\equiv }d\text{ and }{b}^{2}d\equiv d\hfill \\ d+3\hfill & \text{if }bd\cancel{\equiv }d\text{ and }{b}^{2}d\cancel{\equiv }d .\hfill \end{array}$$

Proof.

By Remark 19 and Main Theorem 4, to determine $\Delta (D{\prime }_{n,b})$ we may neglect the vertex 0. Moreover, if d > 1, or if there is a vertex of degree d + 2, then we may neglect the vertices which are not a multiple of d.

If $bd\equiv d$ (hence d > 1), then for every k we have $\mathit{bkd}\equiv kd$ hence the vertex degree of kd is d + 1. Now suppose that $bd\cancel{\equiv }d$, and notice that $b^{2}d\equiv d$ holds if and only if for every integer k we have $b^{2}kd\equiv kd$. The latter condition means that the outgoing multiplicative edge at kd overlaps an incoming multiplicative edge. By our assumption on b–1, the additive edges at d do not overlap multiplicative edges. The result follows. □

Theorem 22.

Suppose that b–1 is a unit. Then $\Delta (D{\prime }_{n,b})=d+1$ holds if and only if either $n=2d$ or we have $n=3d$ and $bd\cancel{\equiv }0$. Moreover, we have $\Delta (D{\prime }_{n,b})=d+3$ if and only if $n\ge 6,n\ge 4d$, and $b^{2}d\cancel{\equiv }d$.

Proof.

As in the proof of Theorem 21, we can neglect the vertex 0 and if d > 1, we can also neglect those vertices that are not divisible by d. If $n=2d$, then d = b and b is even, and we only need to remark that the vertex degree for d is d + 1 (the additive edges at d overlap multiplicative ones).

Now suppose $n=3d$. If d = 1, then $\delta (D{\prime }_{3,2})=\Delta (D{\prime }_{3,2})=2=d+1$. Suppose that d > 1 and $bd\cancel{\equiv }0$. Then $b\cancel{\equiv }0\mathrm{mod}3$ and b = d or $b=2d$. Since $b-1$ is a unit, $b=2d$ if $d\equiv 1\mathrm{mod}3$ and b = d if $d\equiv 2\mathrm{mod}3$. In each case, $b\equiv 2\mathrm{mod}3$ and $bd\equiv 2d$. We have $bd\equiv 2d$ and $2bd\equiv d$, hence the outgoing multiplicative edge at each of the vertices d and 2d overlaps an incoming multiplicative edge at this vertex. We further note by Remark 7 that exactly two multiplicative edges overlap additive edges, namely the edge $({(b-1)}^{-1},{(b-1)}^{-1}+1)$ and the edge $(-{(b-1)}^{-1},-{(b-1)}^{-1}-1)$. Then ${(b-1)}^{-1}+1$ is d or 2d modulo n. If ${(b-1)}^{-1}+1\equiv d$, then $-{(b-1)}^{-1}-1\equiv 2d$, while $-{(b-1)}^{-1}-1\equiv d$ if ${(b-1)}^{-1}+1\equiv 2d$. Thus both d and 2d have vertex degree equal to d + 1.

Now suppose that $bd\equiv 0$. Then the vertex degree of both d and 2d is equal to d + 2. There are d distinct incoming multiplicative edges and an outgoing multiplicative edge (towards 0) at each of the vertices d and 2d. By our argument above, exactly one multiplicative edge overlaps an additive edge at each of d and 2d. Thus the vertex degree at d and 2d is equal to d + 2. We note that if n = 4, then b = 2 (since $b-1$ is a unit), a case we have already treated. By inspection, we see that $\Delta (D{\prime }_{5,b})=3=d+2$ for $2\le b\le 4$.

Finally, suppose $n\ge 6$ and $n\ge 4d$. By Remark 7, there exist exactly two multiplicative edges that overlap additive edges. Hence there exists k such that the additive edges at kd do not overlap a multiplicative edge at kd. Thus the vertex degree at kd is at least d + 2 for this value of k. If $b^{2}d\equiv d$, then for every k, the outgoing multiplicative edge at kd overlaps an incoming multiplicative edge, and the degree of kd is at most d + 2. From now on, supposing $b^{2}d\cancel{\equiv }d$, we find a vertex with vertex degree d + 3. We first suppose that d = 1 (thus b is a unit). Then $n\ge 7$, because b and $b-1$ cannot be both units modulo 6 if $2\le b\le 5$. Moreover, there exist three nonconsecutive vertices that are units. If n is odd, this is because we can take the vertices $(1,4,n-1)$. If n is even, this is because $\phi (n)\ge 4$ and each unit modulo n is odd. At least one of the three vertices is suitable because there are at most two additive edges that overlap a multiplicative edge.

If $bd\equiv 0$, there exists k such that the additive edges at kd do not overlap multiplicative ones. Now suppose $bd\cancel{\equiv }0$, and call $d\prime :=\gcd (\frac{n}{d},d)$.

If $d\prime =1$, then for $1\le k\le k\prime \le \frac{n}{d}-1$ we have $\mathit{bkd}\cancel{\equiv }0$ and hence $\mathit{bkd}\cancel{\equiv }bk\prime d$ unless $k=k\prime$. In particular, $(b-1)b^{4}d\cancel{\equiv }0$ (as b–1 is a unit). Thus the vertices $d,bd,b^{2}d$ are distinct and their outgoing multiplicative edges do not overlap incoming multiplicative edges: they are not connected by additive edges (as d > 1), and for at most two of them an additive edge overlaps a multiplicative edge.

Finally, let $d\prime >1$ and set $k:=\frac{n}{dd\prime }$ hence $\mathit{bkd}\equiv 0$. In particular, the outgoing multiplicative edge at kd does not overlap an additive edge, and neither does an incoming multiplicative edge, else we would have $b(kd\pm 1)\equiv kd$ hence $b\equiv \pm kd$, thus $bd\equiv 0$, contradiction. □

The maximum and minimum degree in $D{\prime }_{n,b}$ may also coincide:

Theorem 23.

We have $\delta (D{\prime }_{n,b})=\Delta (D{\prime }_{n,b})$ if and only if n = 3 and b = 2, in which case all vertex degrees in $D{\prime }_{n,b}$ equal 2, or $n\equiv 2\mathrm{mod}4$ and $b=\frac{n}{2}+1$, in which case all vertex degrees in $D{\prime }_{n,b}$ equal 3.

Proof.

Assume that $\delta (D{\prime }_{n,b})=\Delta (D{\prime }_{n,b})$. By Main Theorem 4, we have $\delta (D{\prime }_{n,b})\in \{2,3\}$ and $\Delta (D{\prime }_{n,b})\in \{d+1,d+2,d+3\}$. Thus $\delta (D{\prime }_{n,b})<\Delta (D{\prime }_{n,b})$ if $d\ge 3$, hence d = 1, 2.

Suppose d = 1. Then b is a unit and $\delta (D{\prime }_{n,b})=2$ by the proof of Main Theorem 4. If b–1 is not a unit, then $bd=b\equiv 1$ by Theorem 21, which is impossible. If $b-1$ is a unit, then n = 3 and b = 2 by Theorem 22.

Now suppose that d = 2. Then $\Delta (D{\prime }_{n,b})\ge 3$ by Main Theorem 4. Since $\delta (D{\prime }_{n,b})\in \{2,3\}$, we have that $\delta (D{\prime }_{n,b})=\Delta (D{\prime }_{n,b})=3$. Since $\delta (D{\prime }_{n,b})=3$, it follows by Main Theorem 4 that $b-1$ is not a unit. We now see by Theorem 21 that $bd=2b\equiv d=2$. Hence $b\equiv 1\mathrm{mod}\frac{n}{2}$, implying that $b=\frac{n}{2}+1$. Since d = 2, we observe that $\frac{n}{2}+1$ is even, yielding $n\equiv 2\mathrm{mod}4$.

We now show that if $n\equiv 2\mathrm{mod}4$ and $b=\frac{n}{2}+1$, then in fact we have $\delta (D{\prime }_{n,b})=\Delta (D{\prime }_{n,b})=3$. Let a be a vertex not divisible by d = 2. Then there are no incoming multiplicative edges at a by Remark 8. The outgoing multiplicative edge at a is $(a,a+\frac{n}{2})$. Since $\frac{n}{2}\ge 3$, we see that this edge is not an additive edge, and thus $\mathrm{deg}(a)=3$. Now suppose that the vertex a is divisible by d = 2. Then $ba=(\frac{n}{2}+1)a\equiv a$ and there is a loop at a. Since $b-1$ is not a unit, no multiplicative edge at a overlaps an additive edge by Remark 7. Since there are d = 2 incoming multiplicative edges at a by Remark 8, it follows that $\mathrm{deg}(a)=3$ in this instance also. □

We were further able to characterize the vertices of degree 2:

Theorem 24.

A vertex a of $D{\prime }_{n,b}$ has degree 2 if and only if one of the following holds:

1. b is a unit and a = 0.

2. b is not a unit, $b-1$ is a unit, and $a\equiv {(b-1)}^{-1}$ or $a\equiv -{(b-1)}^{-1}$.

3. b is a unit, $b-1$ is not a unit, and $(b-1)a\equiv 0$.

4. n is odd, $b=n-1$, and $a=\frac{n\pm 1}{2}$.

Proof.

By the proof of Main Theorem 4, $\delta (D{\prime }_{n,b})=2$ if and only if b or $b-1$ is a unit. Moreover, by the same proof, $\mathrm{deg}(0)=2$ if b is a unit.

Now suppose that b is not a unit and $b-1$ is a unit. By the proof of Main Theorem 4 and by Remark 7, $\mathrm{deg}({(b-1)}^{-1})=\mathrm{deg}(-{(b-1)}^{-1})=2$. Furthermore, the multiplicative edge $({(b-1)}^{-1},{(b-1)}^{-1}+1)$ and the multiplicative edge $(-{(b-1)}^{-1},-{(b-1)}^{-1}-1)$ are the only multiplicative edges that overlap an additive edge. Let a be a vertex such that $a\cancel{\equiv }\pm {(b-1)}^{-1}$. Then the outgoing multiplicative edge at a does not overlap an additive edge. Suppose that $a\ne 0$. Since $b-1$ is a unit, there is no loop at a. Since the outgoing multiplicative edge at a does not overlap an additive edge, we see that $\mathrm{deg}(a)>2$. Next suppose that a = 0. Then there is a loop at 0 and the additive edges (0, 1) and $(b-1,0)$ are not multiplicative edges. Moreover, there are $d\ge 2$ incoming multiplicative edges at 0. It follows that $\mathrm{deg}(0)>2$ in this case.

Next suppose that b is a unit and $b-1$ is not a unit. Let a be a vertex such that $(b-1)a\equiv 0$. Then there is a loop at a. Further, no multiplicative edge at a overlaps an additive edge because $b-1$ is not a unit. Since d = 1, there is exactly one incoming multiplicative edge at a. Thus $\mathrm{deg}(a)=2$. Now suppose that a is a vertex such that $(b-1)a\cancel{\equiv }0$. Then there is no loop at a. By the argument above, the outgoing edge at a does not overlap an additive edge. Hence $\mathrm{deg}(a)>2$ in this instance.

Finally, suppose that both b and $b-1$ are units. Then n must be odd and we have d = 1. Let a be a nonzero vertex such that $\mathrm{deg}(a)=2$. Since $b-1$ is a unit, there is no loop at a. Since b is a unit, there is exactly one incoming multiplicative edge at a. It follows that $\mathrm{deg}(a)=2$ if and only if the incoming multiplicative edge at a is an additive edge and the outgoing multiplicative edge at a is also an additive edge. Since $b-1$ is a unit, it follows by Remark 7 that the edges $({(b-1)}^{-1},{(b-1)}^{-1}+1)$ and $(-{(b-1)}^{-1},-{(b-1)}^{-1}-1)$ are the only multiplicative edges that overlap an additive edge. Thus, $\mathrm{deg}(a)=2$ if and only if ${(b-1)}^{-1}+1\equiv -{(b-1)}^{-1}$, which implies that $2{(b-1)}^{-1}\equiv -1$. It now follows that $b-1\equiv -2$. Hence $b=n-1$ and either $$a\equiv {(b-1)}^{-1}\equiv \frac{n-1}{2}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{or}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}a\equiv -{(b-1)}^{-1}\equiv \frac{n+1}{2}.$$ □

6 Chromatic Number

For $n\ge 4$ the simplified divisibility graph $D{\prime }_{n,b}$ is connected, and neither an odd cycle nor a complete graph, so Brooks’ theorem gives $\chi (D{\prime }_{n,b})\le \Delta (D{\prime }_{n,b})$.

Proof

of Main Theorem 5. For the first assertion we may suppose that $n\ge 5$ and also by Main Theorem 4 that d > 1. The subgraph G_d induced by the multiples of d admits a 3-coloring by Remark 11, and we can extend it to a 4-coloring of $D{\prime }_{n,b}$. Indeed, there are no incoming multiplicative edges for the vertices outside G_d, so for $0\le k\le \frac{n}{d}-1$ we can iteratively color the vertices kd + i for $1\le i\le d-1$: the vertex kd + i sees at most two (respectively, three) previously chosen colors for $i\ne d-1$ (respectively, $i=d-1$).

If $n\equiv 2\mathrm{mod}4$, then $D{\prime }_{n,\frac{n}{2}+1}$ has a 2-coloring given by mapping a vertex to its remainder modulo 2 (the multiplication by b maps odd vertices to even vertices, and it maps any even vertex to itself). If $\chi (D{\prime }_{n,b})=2$, then (considering the additive edges) n is even and w.l.o.g. the 2-coloring maps a vertex to its remainder modulo 2. If $b\ne \frac{n}{2}+1$ (respectively, $b=\frac{n}{2}+1$ and $n\equiv 0\mathrm{mod}4$), the vertices 2 and 2b (respectively, 1 and b) are distinct, adjacent, and have the same color. □

Conjecture 4 has been verified with SageMath [8] for $n\le 291$. Moreover, it has been proven in the following cases:

Proposition 25.

If $b^2\equiv 1,bd\equiv d$, or $bd\equiv 0$, then $\chi (D{\prime }_{n,b})\le 3$.

Proof.

In the first case, we can check by hand $D{\prime }_{3,2},D{\prime }_{4,3}$, $D{\prime }_{5,4}$, and for $n\ge 6$ we have $\Delta (D{\prime }_{n,b})\le d+2=3$ by Theorems 21 and 22. In the second case, we get a 3-coloring by assigning to each multiple of d the color 0 and by alternating between 1 and 2 on each interval between two multiples of d. In the third case, we obtain a 3-coloring as follows: assign the color 0 to the vertex 0 and the color 1 to all the other multiples of d; assign colors to the vertices between two multiples of d by alternating between colors 0 and 2 and by assigning the color 1 to vertices adjacent to 0. □

Example 26.

If $n\equiv 0\mathrm{mod}4$, then ${(\frac{n}{2}-1)}^2\equiv 1$ hence $\chi \left(D_{n,\frac{n}{2}-1}\right)\le 3$ by Proposition 25. Moreover, we have the following 3-colorings for $D{\prime }_{n,\frac{n}{2}}$ and $n\equiv 2\mathrm{mod}4$, for $D{\prime }_{n,\frac{n}{2}}$ and $n\equiv 0\mathrm{mod}4$, and for $D{\prime }_{n,\frac{n}{2}-1}$ and $n\equiv 2\mathrm{mod}4$, respectively:

Above, the polygon consists of the additive edges, with 0 at the bottom.

If $n\equiv 2\mathrm{mod}3$ (respectively, $n\equiv 1\mathrm{mod}6$), then a 3-coloring for $D{\prime }_{n,n-2}$ can be defined by mapping a vertex to its remainder modulo 3 (respectively, additionally replacing the color of 0 to be 2). Indeed, for all a the vertices $a-1,a,a+1$ have distinct colors, so we are left to show that a and ba have distinct colors for every $a\ne 0$: the remainder of ba modulo n is $n-2a$ or $2n-2a$, thus not congruent to a modulo 3.

Similarly, if $k\ge 2$ is not divisible by 3, then $D{\prime }_{3k,k+1}$ and $D{\prime }_{3k,2k+1}$ have a 3-coloring by mapping a vertex to its remainder modulo 3 (as $b\cancel{\equiv }1\mathrm{mod}3$ and $n\equiv 0\mathrm{mod}3$, the remainder of ba modulo n is not congruent to a modulo 3 if 3 does not divide a; furthermore, if 3 does divide a there is a loop at the vertex a).

7 Planarity

To investigate planarity for divisibility graphs, we may consider simplified divisibility graphs instead, as planarity is not affected by loops nor by multiple edges.

Example 27.

The graph $D{\prime }_{n,n-1}$, and for n even the graphs $D{\prime }_{n,\frac{n}{2}}$ and $D{\prime }_{n,\frac{n}{2}-1}$ are planar. Indeed, $D{\prime }_{n,n-1}$ can be drawn as in Figure 18, while the graph $D{\prime }_{n,\frac{n}{2}}$ (respectively, $D{\prime }_{n,\frac{n}{2}-1}$) can be drawn as in Figure 19 (respectively, Figure 20), where the dashed edge $(\frac{n}{2},0)$ is not present if $\frac{n}{2}$ is odd (respectively, even).

Fig. 18 $D{\prime }_{n,n-1}$ for n odd and for n even.

Fig. 19 $D{\prime }_{n,\frac{n}{2}}$.

Fig. 20 $D{\prime }_{n,\frac{n}{2}-1}$.

Wagner’s theorem states that a graph is planar if and only if it does not contain as a minor K₅ nor $K_{3,3}$, which are the following graphs:

For example, $D{\prime }_{15,6}$ contains a minor isomorphic to K₅. We will often exhibit a minor isomorphic to $K_{3,3}$: the vertices will be listed in cyclic order; the vertices are $\{x_1,x_2,x_3,b{x}_1,b{x}_2,b{x}_3\}$, and $x_1,x_2,x_3$ will be marked in bold.

Proposition 28.

If b = 2 and $n\ge 10$, or b = 3 and $n\ge 12$, or $b\ge 4$ and $n\ge 3b$, then $D{\prime }_{n,b}$ is nonplanar.

Proof.

The minors isomorphic to $K_{3,3}$ are $(\mathbf{3},\mathbf{4},\mathbf{5},6,8,10),(\mathbf{2},\mathbf{3},\mathbf{4},6,9,12)$, and $(\mathbf{1},\mathbf{2},\mathbf{3},b,2b,3b)$, respectively. □

By Example 27, an odd integer $n\ge 13$ (respectively, an even integer $n\ge 16$) satisfies Conjecture 5 if and only if $D{\prime }_{n,b}$ is nonplanar for all $b\ne n-1$ (respectively, $b\ne \frac{n}{2},\frac{n}{2}-1,n-1$). We verified with SageMath [8] that all prime numbers in the range from 13 to 4391 and all integers $n\le 1186$ satisfy Conjecture 5.

Proposition 29.

If Conjecture 5 holds for all n that are prime numbers, then it holds for all n.

To prove this, we make use of the following:

Lemma 30.

If n satisfies Conjecture 5, then the same holds for 2n. If n is odd and it satisfies Conjecture 5, then the same holds for kn for every positive odd integer $1<k\le n$.

Proof.

For n odd, $D{\prime }_{2n,n+1}$ is nonplanar, as can be seen by considering the minor $(\mathbf{1},\mathbf{3},\mathbf{5},n+1,n+3,n+5)$. For n even, $D{\prime }_{2n,\frac{n}{2}-1}$ and $D{\prime }_{2n,\frac{n}{2}}$ are nonplanar by Proposition 28, while the graphs $D{\prime }_{2n,n+\frac{n}{2}-1}$ and $D{\prime }_{2n,n+\frac{n}{2}}$ are nonplanar because of the minor $(\mathbf{1},\mathbf{4},\mathbf{n}+\mathbf{2},n+\frac{n}{2}-1,2n-4,2n-1)$ and the minor $(\mathbf{1},\frac{n}{2},n,n+\frac{n}{2},\mathbf{2}\mathbf{n}-\mathbf{5},\mathbf{2}\mathbf{n}-\mathbf{2})$, respectively. Remark 9 settles all remaining cases of the first assertion, and the cases $b\cancel{\equiv }0,1,n-1$ of the second assertion. To conclude, we may suppose that $b\in \{\mathcal{l}n,\mathcal{l}n+1,\mathcal{l}n-1\}$ where $1\le l\le k-1$. If $b=n+1$ and k > 3, then $D{\prime }_{kn,n}$ is nonplanar by Proposition 28. In the remaining cases $D{\prime }_{kn,n}$ is not planar because of the following minors:

Table

b	minor isomorphic to $K_{3,3}$
ln–1, $l<\frac{k}{2}$	$(\mathbf{1},\mathbf{2},\mathbf{k},ln-1,2ln-2,kn-k)$
ln–1, $\frac{k}{2}<l$	$(\mathbf{1},\mathbf{k},(k-l)n+1,ln-1,kn-k,\mathbf{kn}-\mathbf{1})$
ln, $l<\frac{k}{2}$	$(0,\mathbf{1},\mathbf{2},\mathbf{k},ln,2ln)$
ln, $l=\frac{k+1}{2}$, k = 3	$(0,\mathbf{1},n,\frac{\mathbf{3}}{\mathbf{2}}\mathbf{n}+\frac{\mathbf{9}}{\mathbf{2}},2n,\mathbf{3}\mathbf{n}-\mathbf{1})$
ln, $l=\frac{k+1}{2}$, k > 3	$(\mathbf{1},\mathbf{3},\mathbf{k}-\mathbf{2},\frac{k+1}{2}n,\frac{k+1}{2}3n,kn-k-1)$
ln, $\frac{k+1}{2}<l$	$(0,\mathbf{1},(k-l)n,\mathbf{a},ln,\mathbf{kn}-\mathbf{1})$
ln + 1, $\frac{k}{2}<l$	$(\mathbf{1},\mathbf{k}+\mathbf{1},(k-l)n-1,ln+1,ln+k+1,\mathbf{kn}-\mathbf{1})$
ln + 1, $l<\frac{k}{2},l\ne 1,\frac{k-1}{2}$	$(\mathbf{1},\mathbf{2},\mathbf{k}+\mathbf{2},ln+1,2ln+2,2ln+k+2)$
ln + 1, $l=\frac{k-1}{2}$	$(\mathbf{1},\mathbf{2},n-2,\frac{k-1}{2}n+1,(k-2)n+2,\mathbf{kn}-\mathbf{2})$

Above, a denotes a multiple of k such that $kn-ln<\mathbf{a}<ln$. □

Proof of Proposition 29.

An odd number $\ge 13$ is an odd multiple of a number $\ge 13$ which is prime or $\le 121$, so we conclude by Lemma 30. An even number $\ge 16$ is a number for which the conjecture has been verified or it is a power of 2 times an odd number $\ge 13$, so we conclude by Lemma 30 and the previous case. □

Notice that, in case the lower bound for n in Conjecture 5 gets updated, one could still reduce to prime numbers and an explicit finite number set.

In this article we have raised several questions and we have answered some of them. The interested reader can try to prove or disprove our conjectures. Moreover, there are other notions for graphs that deserve to be investigated for divisibility graphs hence there are many open research directions. Some of these investigations are accessible to students, so they are suitable for undergraduate research.

Acknowledgments

We thank MATH-segnale for introducing divisibility graphs with [2]. We thank Anne-Julie Bertinchamps, Tia De Waha, Sergei Merkulov, Hugo Parlier, Emiliano Torti, and last but not least, the anonymous referees for their very valuable comments and also for supporting our project with enthusiasm.

Additional information

Notes on contributors

Antonella Perucca

ANTONELLA PERUCCA studied at Scuola Normale Superiore in Pisa and then continued her career as a number theorist in Italy, Switzerland, Belgium, Germany, and Luxembourg. She is also active in recreational mathematics, didactics, and outreach.

Department of Mathematics, University of Luxembourg, 4634 Esch, Luxembourg

[email protected]

Tim Seuré

TIM SEURÉ has received his Bachelor in mathematics in 2021 and is about to finish his Master’s studies. Afterwards, he will be working towards a Ph.D. in computational number theory and cryptography.

Department of Mathematics, University of Luxembourg, 4634 Esch, Luxembourg

[email protected]

Vincent Wolff

VINCENT WOLFF entered the University of Luxembourg in 2016. He is now doing a Ph.D. in Mathematical Physics under the supervision of Prof. Dr. Sergei Merkulov.

Department of Mathematics, University of Luxembourg, 4634 Esch, Luxembourg

[email protected]