×

On a connection of number theory with graph theory. (English) Zbl 1080.11004

Summary: We assign to each positive integer \(n\) a digraph whose set of vertices is \(H=\{0,1,\dots ,n-1\}\) and for which there is a directed edge from \(a\in H\) to \(b\in H\) if \(a^2\equiv b\pmod n\). We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.

MSC:

11A07 Congruences; primitive roots; residue systems
05C20 Directed graphs (digraphs), tournaments
11A51 Factorization; primality
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] S. Bryant: Groups, graphs, and Fermat’s last theorem. Amer. Math. Monthly 74 (1967), 152-156. · Zbl 0163.02605 · doi:10.2307/2315605
[2] R. D. Carmichael: Note on a new number theory function. Bull. Amer. Math. Soc. 16 (1910), 232-238. · JFM 41.0226.04 · doi:10.1090/S0002-9904-1910-01892-9
[3] G. Chartrand and L. Lesniak: Graphs and Digraphs (Third edition). Chapman & Hall, London, 1996. · Zbl 0890.05001
[4] G. Chassé: Applications d’un corps fini dans lui-même. Dissertation, Univ. de Rennes I, 1984.
[5] G. Chassé: Combinatorial cycles of a polynomial map over a commutative field. Discrete Math. 61 (1986), 21-26. · Zbl 0596.12020 · doi:10.1016/0012-365X(86)90024-5
[6] F. Harary: Graph Theory. Addison-Wesley Publ. Company, London, 1969. · Zbl 0196.27202
[7] P. Kiss: Egy binom kongruenciáról. Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei (1978), 457-464.
[8] M. Křížek, F. Luca and L. Somer: 17 Lectures on the Fermat Numbers. From Number Theory to Geometry. Springer-Verlag, New York, 2001.
[9] M. Křížek and L. Somer: A necessary and sufficient condition for the primality of Fermat numbers. Math. Bohem. 126 (2001), 541-549. · Zbl 0993.11002
[10] F. Robert: Discrete Iterations. Springer Series in Comput. Math. Vol. 6. Springer-Verlag, Berlin, 1986.
[11] T. D. Rogers: The graph of the square mapping on the prime fields. Discrete Math. 148 (1996), 317-324. · Zbl 0843.05048 · doi:10.1016/0012-365X(94)00250-M
[12] L. Szalay: A discrete iteration in number theory. BDTF Tud. Közl. 8 (1992), 71-91. · Zbl 0801.11011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.