| Title:
|
On a connection of number theory with graph theory (English) |
| Author:
|
Somer, Lawrence |
| Author:
|
Křížek, Michal |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
2 |
| Year:
|
2004 |
| Pages:
|
465-485 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Fermat numbers |
| Keyword:
|
Chinese remainder theorem |
| Keyword:
|
primality |
| Keyword:
|
group theory |
| Keyword:
|
digraphs |
| MSC:
|
05C20 |
| MSC:
|
11A07 |
| MSC:
|
11A15 |
| MSC:
|
11A51 |
| MSC:
|
20K01 |
| idZBL:
|
Zbl 1080.11004 |
| idMR:
|
MR2059267 |
| . |
| Date available:
|
2009-09-24T11:14:38Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127904 |
| . |
| Reference:
|
[1] S. Bryant: Groups, graphs, and Fermat’s last theorem.Amer. Math. Monthly 74 (1967), 152–156. Zbl 0163.02605, MR 0207824, 10.2307/2315605 |
| Reference:
|
[2] R. D. Carmichael: Note on a new number theory function.Bull. Amer. Math. Soc. 16 (1910), 232–238. MR 1558896, 10.1090/S0002-9904-1910-01892-9 |
| Reference:
|
[3] G. Chartrand and L. Lesniak: Graphs and Digraphs (Third edition).Chapman & Hall, London, 1996. MR 1408678 |
| Reference:
|
[4] G. Chassé: Applications d’un corps fini dans lui-même.Dissertation, Univ. de Rennes I, 1984. MR 0782298 |
| Reference:
|
[5] G. Chassé: Combinatorial cycles of a polynomial map over a commutative field.Discrete Math. 61 (1986), 21–26. MR 0850926, 10.1016/0012-365X(86)90024-5 |
| Reference:
|
[6] F. Harary: Graph Theory.Addison-Wesley Publ. Company, London, 1969. Zbl 0196.27202, MR 0256911 |
| Reference:
|
[7] P. Kiss: Egy binom kongruenciáról.Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei (1978), 457–464. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[10] F. Robert: Discrete Iterations. Springer Series in Comput. Math. Vol. 6.Springer-Verlag, Berlin, 1986. MR 0851186 |
| Reference:
|
[11] T. D. Rogers: The graph of the square mapping on the prime fields.Discrete Math. 148 (1996), 317–324. Zbl 0843.05048, MR 1368298, 10.1016/0012-365X(94)00250-M |
| Reference:
|
[12] L. Szalay: A discrete iteration in number theory.BDTF Tud. Közl. 8 (1992), 71–91. (Hungarian) Zbl 0801.11011 |
| . |
