On a connection of number theory with graph theory

Lawrence Somer; Michal Křížek

Czechoslovak Mathematical Journal (2004)

  • Volume: 54, Issue: 2, page 465-485
  • ISSN: 0011-4642

Abstract

top
We assign to each positive integer n a digraph whose set of vertices is H = { 0 , 1 , , n - 1 } and for which there is a directed edge from a H to b H if a 2 b ( m o d 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.

How to cite

top

Somer, Lawrence, and Křížek, Michal. "On a connection of number theory with graph theory." Czechoslovak Mathematical Journal 54.2 (2004): 465-485. <http://eudml.org/doc/30876>.

@article{Somer2004,
abstract = {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.},
author = {Somer, Lawrence, Křížek, Michal},
journal = {Czechoslovak Mathematical Journal},
keywords = {Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs; Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs},
language = {eng},
number = {2},
pages = {465-485},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On a connection of number theory with graph theory},
url = {http://eudml.org/doc/30876},
volume = {54},
year = {2004},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 2
SP - 465
EP - 485
AB - 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.
LA - eng
KW - Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs; Fermat numbers; Chinese remainder theorem; primality; group theory; digraphs
UR - http://eudml.org/doc/30876
ER -

References

top
  1. 10.2307/2315605, Amer. Math. Monthly 74 (1967), 152–156. (1967) Zbl0163.02605MR0207824DOI10.2307/2315605
  2. 10.1090/S0002-9904-1910-01892-9, Bull. Amer. Math. Soc. 16 (1910), 232–238. (1910) MR1558896DOI10.1090/S0002-9904-1910-01892-9
  3. Graphs and Digraphs (Third edition), Chapman & Hall, London, 1996. (1996) MR1408678
  4. Applications d’un corps fini dans lui-même, Dissertation, Univ. de Rennes  I, 1984. (1984) MR0782298
  5. 10.1016/0012-365X(86)90024-5, Discrete Math. 61 (1986), 21–26. (1986) MR0850926DOI10.1016/0012-365X(86)90024-5
  6. Graph Theory, Addison-Wesley Publ. Company, London, 1969. (1969) Zbl0196.27202MR0256911
  7. Egy binom kongruenciáról, Az Egi Ho Si Mihn Tanárképzó Fóiskola füzetei (1978), 457–464. (1978) 
  8. 17  Lectures on the Fermat Numbers. From Number Theory to Geometry, Springer-Verlag, New York, 2001. (2001) MR1866957
  9. A necessary and sufficient condition for the primality of Fermat numbers, Math. Bohem. 126 (2001), 541–549. (2001) MR1970256
  10. Discrete Iterations. Springer Series in Comput. Math. Vol. 6, Springer-Verlag, Berlin, 1986. (1986) MR0851186
  11. 10.1016/0012-365X(94)00250-M, Discrete Math. 148 (1996), 317–324. (1996) Zbl0843.05048MR1368298DOI10.1016/0012-365X(94)00250-M
  12. A discrete iteration in number theory, BDTF Tud. Közl. 8 (1992), 71–91. (Hungarian) (1992) Zbl0801.11011

Citations in EuDML Documents

top
  1. J. Skowronek-Kaziów, Properties of digraphs connected with some congruence relations
  2. Lawrence Somer, Michal Křížek, On semiregular digraphs of the congruence x k y ( mod n )
  3. Walter Carlip, Martina Mincheva, Symmetry of iteration graphs
  4. Tengxia Ju, Meiyun Wu, On iteration digraph and zero-divisor graph of the ring n
  5. Michal Křížek, Lawrence Somer, Sophie Germain little suns
  6. Uzma Ahmad, Syed Husnine, Characterization of power digraphs modulo n
  7. Uzma Ahmad, Husnine Syed, On the heights of power digraphs modulo n
  8. Yangjiang Wei, Jizhu Nan, Gaohua Tang, The cubic mapping graph for the ring of Gaussian integers modulo n
  9. Uzma Ahmad, Muqadas Moeen, The classification of finite groups by using iteration digraphs
  10. Michal Křížek, Lawrence Somer, 17 necessary and sufficient conditions for the primality of Fermat numbers

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.