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

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]