About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Somer, Lawrence ; Křížek, Michal
The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$. (English). Czechoslovak Mathematical Journal, vol. 61 (2011), issue 2, pp. 337-358
MSC: 05C20, 11A07, 11A15, 20K01 | MR 2905408 | Zbl 1249.11006 | DOI: 10.1007/s10587-011-0079-x
Keywords:
Sophie Germain primes; Fermat primes; primitive roots; Chinese Remainder Theorem; congruence; digraphs
Summary:
We assign to each pair of positive integers $n$ and $k\ge 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.
References:
[1] Carlip, W., Mincheva, M.: Symmetry of iteration digraphs. Czech. Math. J. 58 (2008), 131-145. DOI 10.1007/s10587-008-0009-8 | MR 2402530
[2] Chou, W.-S., Shparlinski, I. E.: On the cycle structure of repeated exponentiation modulo a prime. J. Number Theory 107 (2004), 345-356. DOI 10.1016/j.jnt.2004.04.005 | MR 2072394 | Zbl 1060.11059
[3] Friendlander, J. B., Pomerance, C., Shparlinski, I. E.: Period of the power generator and small values of Carmichael's function. Math. Comput. 70 (2001), 1591-1605; Corrigendum ibid. 71 (2002), 1803-1806. MR 1836921
[4] Hartnell, B., Rall, D. F.: Domination in Cartesian products: Vizing's conjecture. Domination in Graphs. Advanced Topics Dekker New York T. Waynes, S. T. Hedetniemi, P. J. Slater (1998), 163-189. MR 1605692 | Zbl 0890.05035
[5] Křížek, M., Luca, F., Somer, L.: 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics, Vol. 9. Springer New York (2001). MR 1866957
[6] Kurlberg, P., Pomerance, C.: On the periods of the linear congruential and power generators. Acta Arith. (2005), 119 149-169. MR 2167719 | Zbl 1080.11059
[7] Lucheta, C., Miller, E., Reiter, C.: Digraphs from powers modulo $p$. Fibonacci Q. 34 (1996), 226-239. MR 1390409 | Zbl 0855.05067
[8] Martin, G., Pomerance, C.: The iterated Carmichael $\lambda$-function and the number of cycles of the power generator. Acta Arith. (2005), 118 305-335. MR 2165548 | Zbl 1109.11046
[9] Niven, I., Zuckerman, H. S., Montgomery, H. L.: An Introduction to the Theory of Numbers. 5th ed. John Wiley & Sons New York (1991). MR 1083765 | Zbl 0742.11001
[10] Somer, L., Křížek, M.: On a connection of number theory with graph theory. Czech. Math. J. 54 (2004), 465-485. DOI 10.1023/B:CMAJ.0000042385.93571.58 | MR 2059267
[11] Somer, L., Křížek, M.: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174-2185. DOI 10.1016/j.disc.2005.12.026 | MR 2255611
[12] Somer, L., Křížek, M.: On semiregular digraphs of the congruence $x^k\equiv y\pmod n$. Commentat. Math. Univ. Carol. 48 (2007), 41-58. MR 2338828
[13] Somer, L., Křížek, M.: On symmetric digraphs of the congruence $x^k\equiv y\pmod n$. Discrete Math. 309 (2009), 1999-2009. DOI 10.1016/j.disc.2008.04.009 | MR 2510326
[14] Szalay, L.: A discrete iteration in number theory. Berzseneyi Dániel Tanárk. Föisk. Tud. Közl., Termtud. 8 (1992), 71-91 Hungarian. Zbl 0801.11011
[15] Vasiga, T., Shallit, J.: On the iteration of certain quadratic maps over GF$(p)$. Discrete Math. 277 (2004), 219-240. DOI 10.1016/S0012-365X(03)00158-4 | MR 2033734 | Zbl 1045.11086
[16] Wilson, B.: Power digraphs modulo $n$. Fibonacci Q. 36 (1998), 229-239. MR 1627384 | Zbl 0936.05049
Partner of
EuDML logo