# Article

Full entry | PDF   (0.3 MB)
Keywords:
Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs
Summary:
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.
References:
[1] S.  Bryant: Groups, graphs, and Fermat’s last theorem. Amer. Math. Monthly 74 (1967), 152–156. DOI 10.2307/2315605 | MR 0207824 | Zbl 0163.02605
[2] R. D. Carmichael: Note on a new number theory function. Bull. Amer. Math. Soc. 16 (1910), 232–238. DOI 10.1090/S0002-9904-1910-01892-9 | MR 1558896
[3] G. Chartrand and L.  Lesniak: Graphs and Digraphs (Third edition). Chapman & Hall, London, 1996. MR 1408678
[4] G. Chassé: Applications d’un corps fini dans lui-même. Dissertation, Univ. de Rennes  I, 1984. MR 0782298
[5] G. Chassé: Combinatorial cycles of a polynomial map over a commutative field. Discrete Math. 61 (1986), 21–26. DOI 10.1016/0012-365X(86)90024-5 | MR 0850926
[6] F. Harary: Graph Theory. Addison-Wesley Publ. Company, London, 1969. MR 0256911 | Zbl 0196.27202
[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 1866957
[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 1970256
[10] F. Robert: Discrete Iterations. Springer Series in Comput. Math. Vol. 6. Springer-Verlag, Berlin, 1986. MR 0851186
[11] T. D. Rogers: The graph of the square mapping on the prime fields. Discrete Math. 148 (1996), 317–324. DOI 10.1016/0012-365X(94)00250-M | MR 1368298 | Zbl 0843.05048
[12] L. Szalay: A discrete iteration in number theory. BDTF Tud. Közl. 8 (1992), 71–91. (Hungarian) Zbl 0801.11011

Partner of