The structure of digraphs associated with the congruence \(x^k\equiv y \pmod n\). (English) Zbl 1249.11006

Summary: We assign to each pair of positive integers \(n\) and \(k\geq 2\) a digraph \(G(n,k)\) 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^k\equiv b\pmod n\). We investigate the structure of \(G(n,k)\). In particular, upper bounds are given for the longest cycle in \(G(n,k)\). We find subdigraphs of \(G(n,k)\), called fundamental constituents of \(G(n,k)\), for which all trees attached to cycle vertices are isomorphic.


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


[1] W. Carlip, M. Mincheva: Symmetry of iteration digraphs. Czech. Math. J. 58 (2008), 131–145. · Zbl 1174.05048 · doi:10.1007/s10587-008-0009-8
[2] W.-S. Chou, I.E. Shparlinski: On the cycle structure of repeated exponentiation modulo a prime. J. Number Theory 107 (2004), 345–356. · Zbl 1060.11059 · doi:10.1016/j.jnt.2004.04.005
[3] J.B. Friendlander, C. Pomerance, I.E. Shparlinski: Period of the power generator and small values of Carmichael’s function. Math. Comput. 70 (2001), 1591–1605; Corrigendum ibid. 71 (2002), 1803–1806. · Zbl 1029.11043
[4] B. Hartnell, D. F. Rall: Domination in Cartesian products: Vizing’s conjecture. Domination in Graphs. Advanced Topics (T. Waynes, S.T. Hedetniemi, P. J. Slater, eds.). Dekker, New York, 1998, pp. 163–189. · Zbl 0890.05035
[5] M. Křížek, F. Luca, L. Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics, Vol. 9. Springer, New York, 2001.
[6] P. Kurlberg, C. Pomerance: On the periods of the linear congruential and power generators. Acta Arith. 119 (2005), 149–169. · Zbl 1080.11059 · doi:10.4064/aa119-2-2
[7] C. Lucheta, E. Miller, C. Reiter: Digraphs from powers modulo p. Fibonacci Q. 34 (1996), 226–239. · Zbl 0855.05067
[8] G. Martin, C. Pomerance: The iterated Carmichael {\(\lambda\)}-function and the number of cycles of the power generator. Acta Arith. 118 (2005), 305–335. · Zbl 1109.11046 · doi:10.4064/aa118-4-1
[9] I. Niven, H. S. Zuckerman, H. L. Montgomery: An Introduction to the Theory of Numbers. 5th ed. John Wiley & Sons, New York, 1991. · Zbl 0742.11001
[10] L. Somer, M. Křížek: On a connection of number theory with graph theory. Czech. Math. J. 54 (2004), 465–485. · Zbl 1080.11004 · doi:10.1023/B:CMAJ.0000042385.93571.58
[11] L. Somer, M. Křížek: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174–2185. · Zbl 1161.05323 · doi:10.1016/j.disc.2005.12.026
[12] L. Somer, M. Křížek: On semiregular digraphs of the congruence x k y (mod n). Commentat. Math. Univ. Carol. 48 (2007), 41–58.
[13] L. Somer, M. Křížek: On symmetric digraphs of the congruence x k y (mod n). Discrete Math. 309 (2009), 1999–2009. · Zbl 1208.05041 · doi:10.1016/j.disc.2008.04.009
[14] L. Szalay: A discrete iteration in number theory. Berzseneyi Dániel Tanárk. Föisk. Tud. Közl., Termtud. 8 (1992), 71–91. (In Hungarian.)
[15] T. Vasiga, J. Shallit: On the iteration of certain quadratic maps over GF(p). Discrete Math. 277 (2004), 219–240. · Zbl 1045.11086 · doi:10.1016/S0012-365X(03)00158-4
[16] B. Wilson: Power digraphs modulo n. Fibonacci Q. 36 (1998), 229–239. · Zbl 0936.05049
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.