| Title:
|
The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$ (English) |
| Author:
|
Somer, Lawrence |
| Author:
|
Křížek, Michal |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
61 |
| Issue:
|
2 |
| Year:
|
2011 |
| Pages:
|
337-358 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Sophie Germain primes |
| Keyword:
|
Fermat primes |
| Keyword:
|
primitive roots |
| Keyword:
|
Chinese Remainder Theorem |
| Keyword:
|
congruence |
| Keyword:
|
digraphs |
| MSC:
|
05C20 |
| MSC:
|
11A07 |
| MSC:
|
11A15 |
| MSC:
|
20K01 |
| idZBL:
|
Zbl 1249.11006 |
| idMR:
|
MR2905408 |
| DOI:
|
10.1007/s10587-011-0079-x |
| . |
| Date available:
|
2011-06-06T10:27:45Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141538 |
| . |
| Reference:
|
[1] Carlip, W., Mincheva, M.: Symmetry of iteration digraphs.Czech. Math. J. 58 (2008), 131-145. MR 2402530, 10.1007/s10587-008-0009-8 |
| Reference:
|
[2] Chou, W.-S., Shparlinski, I. E.: On the cycle structure of repeated exponentiation modulo a prime.J. Number Theory 107 (2004), 345-356. Zbl 1060.11059, MR 2072394, 10.1016/j.jnt.2004.04.005 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0890.05035, MR 1605692 |
| Reference:
|
[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 |
| Reference:
|
[6] Kurlberg, P., Pomerance, C.: On the periods of the linear congruential and power generators.Acta Arith. (2005), 119 149-169. Zbl 1080.11059, MR 2167719 |
| Reference:
|
[7] Lucheta, C., Miller, E., Reiter, C.: Digraphs from powers modulo $p$.Fibonacci Q. 34 (1996), 226-239. Zbl 0855.05067, MR 1390409 |
| Reference:
|
[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. Zbl 1109.11046, MR 2165548 |
| Reference:
|
[9] Niven, I., Zuckerman, H. S., Montgomery, H. L.: An Introduction to the Theory of Numbers. 5th ed.John Wiley & Sons New York (1991). Zbl 0742.11001, MR 1083765 |
| Reference:
|
[10] Somer, L., Křížek, M.: On a connection of number theory with graph theory.Czech. Math. J. 54 (2004), 465-485. MR 2059267, 10.1023/B:CMAJ.0000042385.93571.58 |
| Reference:
|
[11] Somer, L., Křížek, M.: Structure of digraphs associated with quadratic congruences with composite moduli.Discrete Math. 306 (2006), 2174-2185. MR 2255611, 10.1016/j.disc.2005.12.026 |
| Reference:
|
[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 |
| Reference:
|
[13] Somer, L., Křížek, M.: On symmetric digraphs of the congruence $x^k\equiv y\pmod n$.Discrete Math. 309 (2009), 1999-2009. MR 2510326, 10.1016/j.disc.2008.04.009 |
| Reference:
|
[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 |
| Reference:
|
[15] Vasiga, T., Shallit, J.: On the iteration of certain quadratic maps over GF$(p)$.Discrete Math. 277 (2004), 219-240. Zbl 1045.11086, MR 2033734, 10.1016/S0012-365X(03)00158-4 |
| Reference:
|
[16] Wilson, B.: Power digraphs modulo $n$.Fibonacci Q. 36 (1998), 229-239. Zbl 0936.05049, MR 1627384 |
| . |
