Geodesic
On a connection of number theory with graph theory
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 465-485
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We assign to each positive integer $n$ a digraph whose set of vertices is $H=\lbrace 0,1,\dots ,n-1\rbrace $ and for which there is a directed edge from $a\in H$ to $b\in H$ if $a^2\equiv b\hspace{4.44443pt}(\@mod \; n)$. We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.
We assign to each positive integer $n$ a digraph whose set of vertices is $H=\lbrace 0,1,\dots ,n-1\rbrace $ and for which there is a directed edge from $a\in H$ to $b\in H$ if $a^2\equiv b\hspace{4.44443pt}(\@mod \; n)$. We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.
Classification : 05C20, 11A07, 11A15, 11A51, 20K01
Keywords: Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs 
@article{CMJ_2004_54_2_a18,
     author = {Somer, Lawrence and K\v{r}{\'\i}\v{z}ek, Michal},
     title = {On a connection of number theory with graph theory},
     journal = {Czechoslovak Mathematical Journal},
     pages = {465--485},
     year = {2004},
     volume = {54},
     number = {2},
     mrnumber = {2059267},
     zbl = {1080.11004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a18/}
}
TY  - JOUR
AU  - Somer, Lawrence
AU  - Křížek, Michal
TI  - On a connection of number theory with graph theory
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 465
EP  - 485
VL  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a18/
LA  - en
ID  - CMJ_2004_54_2_a18
ER  - 
%0 Journal Article
%A Somer, Lawrence
%A Křížek, Michal
%T On a connection of number theory with graph theory
%J Czechoslovak Mathematical Journal
%D 2004
%P 465-485
%V 54
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a18/
%G en
%F CMJ_2004_54_2_a18
Somer, Lawrence; Křížek, Michal. On a connection of number theory with graph theory. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 465-485. http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a18/

[1] S.  Bryant: Groups, graphs, and Fermat’s last theorem. Amer. Math. Monthly 74 (1967), 152–156. | DOI | MR | Zbl

[2] R. D. Carmichael: Note on a new number theory function. Bull. Amer. Math. Soc. 16 (1910), 232–238. | DOI | MR

[3] G. Chartrand and L.  Lesniak: Graphs and Digraphs (Third edition). Chapman & Hall, London, 1996. | MR

[4] G. Chassé: Applications d’un corps fini dans lui-même. Dissertation, Univ. de Rennes  I, 1984. | MR

[5] G. Chassé: Combinatorial cycles of a polynomial map over a commutative field. Discrete Math. 61 (1986), 21–26. | DOI | MR

[6] F. Harary: Graph Theory. Addison-Wesley Publ. Company, London, 1969. | MR | Zbl

[7] P. Kiss: Egy binom kongruenciáról. Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei (1978), 457–464.

[8] M. Křížek, F. Luca and L. Somer: 17  Lectures on the Fermat Numbers. From Number Theory to Geometry. Springer-Verlag, New York, 2001. | MR

[9] M. Křížek and L.  Somer: A necessary and sufficient condition for the primality of Fermat numbers. Math. Bohem. 126 (2001), 541–549. | MR

[10] F. Robert: Discrete Iterations. Springer Series in Comput. Math. Vol. 6. Springer-Verlag, Berlin, 1986. | MR

[11] T. D. Rogers: The graph of the square mapping on the prime fields. Discrete Math. 148 (1996), 317–324. | DOI | MR | Zbl

[12] L. Szalay: A discrete iteration in number theory. BDTF Tud. Közl. 8 (1992), 71–91. (Hungarian) | Zbl