Geodesic
The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$
Czechoslovak Mathematical Journal, Tome 61 (2011) no. 2, pp. 337-358
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-011-0079-x
Classification : 05C20, 11A07, 11A15, 20K01
Keywords: Sophie Germain primes; Fermat primes; primitive roots; Chinese Remainder Theorem; congruence; digraphs 
@article{10_1007_s10587_011_0079_x,
     author = {Somer, Lawrence and K\v{r}{\'\i}\v{z}ek, Michal},
     title = {The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {337--358},
     year = {2011},
     volume = {61},
     number = {2},
     doi = {10.1007/s10587-011-0079-x},
     mrnumber = {2905408},
     zbl = {1249.11006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-011-0079-x/}
}
TY  - JOUR
AU  - Somer, Lawrence
AU  - Křížek, Michal
TI  - The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$
JO  - Czechoslovak Mathematical Journal
PY  - 2011
SP  - 337
EP  - 358
VL  - 61
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-011-0079-x/
DO  - 10.1007/s10587-011-0079-x
LA  - en
ID  - 10_1007_s10587_011_0079_x
ER  - 
%0 Journal Article
%A Somer, Lawrence
%A Křížek, Michal
%T The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$
%J Czechoslovak Mathematical Journal
%D 2011
%P 337-358
%V 61
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-011-0079-x/
%R 10.1007/s10587-011-0079-x
%G en
%F 10_1007_s10587_011_0079_x
Somer, Lawrence; Křížek, Michal. The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$. Czechoslovak Mathematical Journal, Tome 61 (2011) no. 2, pp. 337-358. doi: 10.1007/s10587-011-0079-x

[1] Carlip, W., Mincheva, M.: Symmetry of iteration digraphs. Czech. Math. J. 58 (2008), 131-145. | DOI | MR

[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 | MR | Zbl

[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

[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 | Zbl

[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

[6] Kurlberg, P., Pomerance, C.: On the periods of the linear congruential and power generators. Acta Arith. (2005), 119 149-169. | MR | Zbl

[7] Lucheta, C., Miller, E., Reiter, C.: Digraphs from powers modulo $p$. Fibonacci Q. 34 (1996), 226-239. | MR | Zbl

[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 | Zbl

[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 | Zbl

[10] Somer, L., Křížek, M.: On a connection of number theory with graph theory. Czech. Math. J. 54 (2004), 465-485. | DOI | MR

[11] Somer, L., Křížek, M.: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174-2185. | DOI | MR

[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

[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 | MR

[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

[15] Vasiga, T., Shallit, J.: On the iteration of certain quadratic maps over GF$(p)$. Discrete Math. 277 (2004), 219-240. | DOI | MR | Zbl

[16] Wilson, B.: Power digraphs modulo $n$. Fibonacci Q. 36 (1998), 229-239. | MR | Zbl

Cité par Sources :