×

Structure of digraphs associated with quadratic congruences with composite moduli. (English) Zbl 1161.05323

Summary: We assign to each positive integer \(n\) a digraph \(G(n)\) whose set of vertices is \(H=\{0,1,\dots,n-1\}\) and for which there exists a directed edge from \(a\in H\) to \(b\in H\) if \(a^2\equiv b\pmod n\). Associated with \(G(n)\) are two disjoint subdigraphs: \(G_1(n)\) and \(G_2(n)\) whose union is \(G(n)\). The vertices of \(G_1(n)\) correspond to those residues which are relatively prime to \(n\). The structure of \(G_1(n)\) is well understood. In this paper, we investigate in detail the structure of \(G_2(n)\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)

Keywords:

digraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bryant, S., Groups, graphs, and Fermat’s last theorem, Amer. Math. Monthly, 74, 152-156 (1967) · Zbl 0163.02605
[2] Carmichael, R. D., Note on a new number theory function, Bull. Amer. Math. Soc., 16, 232-238 (1910) · JFM 41.0226.04
[3] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001
[4] G. Chassé, Applications d’un corps fini dans lui-même, Dissertation, Univ. de Rennes I, 1984.; G. Chassé, Applications d’un corps fini dans lui-même, Dissertation, Univ. de Rennes I, 1984.
[5] Chassé, G., Combinatorial cycles of a polynomial map over a commutative field, Discrete Math., 61, 21-26 (1986) · Zbl 0596.12020
[6] Harary, F., Graph Theory (1972), Addison-Wesley Publ. Company: Addison-Wesley Publ. Company London · Zbl 0797.05064
[7] P. Kiss, Egy binom kongruenciáról Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei, 1978, pp. 457-464.; P. Kiss, Egy binom kongruenciáról Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei, 1978, pp. 457-464.
[8] Křížek, M.; Luca, F.; Somer, L., 17 Lectures on the Fermat Numbers, From Number Theory to Geometry (2001), Springer: Springer New York · Zbl 1010.11002
[9] Křížek, M.; Somer, L., Sophie Germain little suns, Math. Slovaca, 54, 433-442 (2004) · Zbl 1108.11002
[10] Robert, F., Discrete Iterations, Springer series in Computational Mathematics, vol. 6 (1986) · Zbl 0639.39005
[11] Rogers, T. D., The graph of the square mapping on the prime fields, Discrete Math., 148, 317-324 (1996) · Zbl 0843.05048
[12] Somer, L.; Křížek, M., On a connection of number theory with graph theory, Czechoslovak Math. J., 54, 465-485 (2004) · Zbl 1080.11004
[13] L. Szalay, A discrete iteration in number theory (Hungarian) BDTF Tud. Közl. VIII. Természettudományok 3, Szombathely, 1992, pp. 71-91.; L. Szalay, A discrete iteration in number theory (Hungarian) BDTF Tud. Közl. VIII. Természettudományok 3, Szombathely, 1992, pp. 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.