 Open Journal of Discrete Mathematics, 2011, 1, 103-107 doi:10.4236/ojdm.2011.13013 Published Online October 2011 (http://www.SciRP.org/journal/ojdm) Copyright © 2011 SciRes. OJDM Symmetric Digraphs from Powers Modulo n Guixin Deng1*, Pingzhi Yuan2 1School of Mathematics, Guang xi Teachers Educati o n U ni versity, Nanning, China 2School of Mathematics, South China Normal University, Guangzhou, China E-mail: *oldlao@163.com, mcsypz@mail.sysu.edu.cn Received June 21, 2011; revised July 25, 2011; accepted August 5, 2011 Abstract For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices i s H = {0,1,2,···, n – 1} and there is a directed edge from a  H to b  H if ak  b(mod n). The digraph G(n,k) is symmetric if its connected components can be partitioned into isomorphic pairs. In this paper we obtain all symmetric G (n,k). Keywords: Congruence, Digraph, Component, Height, Cycle 1. Introduction In , L. Szalay showed that is symmetric if or . In , the authors proved that if p is a Fermat prime, then is not symmetric when or , but it is symmet-ric when . And the following theorem is part of Theorem 5.1 in . ,2Gn85r2mod4nk4modn3r2,2rGp4Theorem 1.1 ( Theorem 5.1) Let 12nnn, where 12and . Suppose that 1, where . Then is symmetric if one of the following conditions holds: 1, 1nnmm12gcd ()1nn ,Gnk2n1i) and 2, 2,mk 12;mk ii) and 3, 2,mk 22;mk iii) and 4m2kIn this paper we prove that if is symmetric, where and ,Gnk2km2n, then or m, k satisfy one of the conditions of the above theorem. 5,m4kThe outline of this paper is as follows. In Section 3 we obtain all symmetric by direct computation. In Section 4 we prove some properties about digraph products which will be useful in the proof of our main theorem. In Section 5 we state and prove the main theo-rem of the present paper. 2,mGk 2. The Carmichael Lambda-Function Before proceeding further, we need to review some pro- perties of the Carmichael lambda-function . nDefinition 2.1 Let n be a positive integer. Then the Carmichael-lambda-function n is defined as follows:  122112111,21,42,22 if 3,1 if is odd prime,lcm ,,,irkkkkreee eirikppp panpppp where pi are distinc primes. The following theorem generalizes the well-known Euler’s theorem which says that if and only if 1mod nangcd ,1an. Theorem 2.1 (Camichael). Let Then ,.anan 1mod nord g if and only if . Moreover, there exists an integer g such that where denotes the multiplicative order of g modulo n. 1an nordg gcd ,,nnFor the proof see [5 , p. 21] 3. The Case n = 2m Let G be a digraph and a be a vertex in G. The indegree of a, denoted by ind(a) is the number of directed edges coming to a, and the outdegree of a is the number of edges leaving a. Particularly, let denote the indegree of a vertex a contained in indkna,Gnk. There are two particular subdigraphs of ,Gnk. Let 1,Gnk be the induced subdigraph of on the set of vertices which are coprime to n and ,Gnk2,Gnk be the induced subdigraph of on the set of vertices which are not coprime with n. We observe that ,Gnkk1Gn, G. X. DENG ET AL. 104 and are disjoint and that 2,Gnk,Gnk 2, that is, no edges goes between and. 1,k G,k1,GnkkGn nkGn 2,Gn,Gn. A,2It is clear that each component of contains a unique cycle, since the component has only a finite number of vertices and each vertex has outdegree 1. The following lemma tells us that every component contained in is determined by its cycle length. knd ,Gnk1t,GnkLemma 3.1 ( Corollary 6.4) Let be a fixed integer. Then any two components in con-taining t-cycle are isomorphic. 1Definition 3.1 We define a height function on the ver-tices and components of . Let c be a vertex of , we define hcto be the minimal nonnegative integer i such that ikc iongruent modulo n to a cycle vertex in ,Gnk if C is a component of ,Gnk cs,Gnk, e suhC we dein indfin1,Gnkd2i.hc peiikknpcCThe indegree and the height function play an impor-tant role in the structure of . We need the fol-lowing results concerning the indegrees and heights. ,GnkpiLemma 3.2 () Let be the prime 1irieinfactorization of n. Let a be a vertex of positive indegree in . Then 11gcdrrii, ,ieiapak where  if 2k and 8ieip, and 1i,ek other-wise. Lemma 3.3 ( Theorem 3.2) Let p be a prime. Let a be a vertex of positive indegree in , and assume that 2Gplpind ep2k and . Then for some positive integer t and 0alktlk1gcd ,ktkeap p where  if 2,2pk and and 3,el 1 otherwise. Lemma 3.4 ( Lemma 3.2) Let p be a prime and e, k be two positive integers. Then ind 0.eeekkpp Lemma 3.5 Let p be a prime and be two positive integers. Let h be the positive integer such 2,e2kthat . Then 1kehhk2,ehhGpk,epGpk. Proof. It is clear that and 2hp And ,.ep k2hG0modkppiev if and only if This proves the Lemma.□ .eikLemma 3.6 Let p be a prime and be two positive integers. Let ,ek2epu where u is the maxi-mal divisor of relatively prime to k. If G is the component of containing 1, then ep,eGpkmin :ihC ivk Proof. Let min :.ihivk Then there exists a di-visor d of v such that d is not a divisor of 1hk. By Theorem 2.1 there exists a vertex ,egGpk such that .epord guv Let moduv edag p. Then epord ad and 1hka is not congruent modulo to 1, but epod1mkahep. We have by the definition of height functio n.  hC hhaConversely if ,aC then there exists such that 1j,ke1modjap then .eporda k Bu t ,eporda uv hence .eporda v And 1mod .hkaep That is .hhC Lemma 3.6 is proved.□ Now we can prove our first result. Theorem 3.1 Let be two positive inte-gers. Then 2, 1km2,mGkis symmetric if and only if one of the following conditions holds. i) 1;m ii) 2,2 ;mk iii) 4, 2;mk iv) 5, 4;mk v) 2m3, 2,.mkkm Proof. The case 3m follows directly by simple computations, so we may assume that , thus 3m222m. We first suppose that is sym-metric. Let 0 and 1 be the components of 2,mkGC C2,mGk containing the vertex 0 and 1, respectively. Then it is easy to see that 0 is just 2. Since the cycle lengths of 0 and 1C are 1, by the assump-tions and Lemma 3.1 we must have, thus C2,mGk0CC1C01hChhC1h. If , then k and mgcd 1nd2,ki2m 02d1min, where 1 if k is odd, and 2 if 2k. We must have 22mk. If 2k, then 1 is a cycle, however is not a cycle. Hence we may assume that C0C2,kr1r and 2h. We have 22m1min:ihhCi k by Lemma 3.6. It implies that 12rhm rh. (3.1) Since 0hhC, by Lemma 3.5 we have 1.hkmkh (3.2) Combining (3.1) and (3.2), we obtain 1121rh hkmrh1, so 3h and 2r. By an easy computation, we have  56,4,2,2 , 5,2,3,1,, ,mkhr ,4,2,2 , or 4,2,2,1 .16,2GBy computations we know that both and 32,4G are symmetric. For and 32,2G,464G, Copyright © 2011 SciRes. OJDM 105G. X. DENG ET AL.by Lemmas 3.2 and 3.3, we have , and for any vertex a in 1 which has positive indegree, . Similarly , 232ind 4816C232ind 4a464ind 16a 8464ind. Thus neither of them are symmetric. Finally, from Theorem 1.1 it is clear that if m, k satisfy one of i) - v), then is symmetric. Theorem 3.1 is proved.□ 2,mkGG 4. Properties of Digraphs Product Given two digraphs 1 and 2G. Let 12G be the digraph whose vertices are the ordered pairs G12,,aa where i and there is a directed edge from iaG12,aab12 1,nn to if there is a directed edge from i to i for In  L. Somer and M. Krizek proved the following fact: Let where 12,bb1,2.iagcd ,12nnn then 12 And the canonical isomorphism is given by where Gnk,,nkGnk,.12,aaaGa In general we have mod ,iianGnkriin12gcd ,nn1,2.,,ki,reerk Gpnnn,k1212eGp,pGp if 1 is the prime factorization of n. We need this fact and the following lemma. ieLemma 4.1 ( Lemma 3.1) Let 12 where . Let iC be a component of 1,iGnk12. And the cycle length of iC is i. Then tCC is a subdigraph of Gn consisting of com-ponents, each having cycles of length . ,k12gcd ,tt12lcm ,tt12gcd ,nn1Lemma 4.2 Let 12 where nnn. If is symmetric, then is symmetric. 1,GnkGnGn12k Gn,k(,)kProof. It follows immediately from Lemma 4.1 and the fact .□ ,,kkGn,GnLemma 4.3 If is symmetric, then ,rGnk is also symmetric for any . 1r,Gnk Proof. Assume that has 2m components, say, 12 2 and for each there exists an isomorphism ,,,mCC C,1, 2,,imi of digraphs: :.mii iCCd If two vertices x, y are in the same component of , then there exists a vertex z and positive inte-gers u, v and ,rGnk moukxzn, which implies that x, y are in the same component of mod vkyzn,Gnk. It follows that if D is a component of , then there exists a such that ,rGnk2,j2m1, ,jDC. Let 11s1ji and where CD21smjiE1CjD, 1 and , are components of . If 1, 2,,js,rGnk lE12s1, 2,,l,xyC and mod ,rkxyn1modk then there exist such that 12,,yy,ryy ,xyn and 1mo dkii .yyn So 1k 1mod xyn and kiy 111moid ,yn we get 11rk mo dxyn and 1 still preserves arrows e consider 1C and 1mCif w as subdigraphf s o,rk 12GnIt fossllows that  and 1 is still an isomor-phism if we consid1C as subdigraphs of er 1C and m,rGnk . Hence Gn is asymmetric. Lemma ved.□ Let G be adigra,rklsh. Let o 4.3 is proG d genote the number of vertices in G, and let ax .cGmMGindc Lemma 4.4 Let G dand Ho digraphs, an be tw ,aG .Hb Then  ind ,indind,abab HMG ,MGMH and GHGH . Proofof thve. It follows imhmediately from te definitions.□ The following lemma is the key lemma for the prf oohe digraph whose set of e main result of this paper. Lemma 4.5 Let mO denote trtices is 011, ,maaa and there is a directed edge from ,aia to ja if ph and ono ly if 0jaaa. Let G and H be twdigras such that all vertices and H have outdegree 1. Then mmOGOH if and only if GH. in G:mmOGOH  et Proof. Assume that is an iso-morphism of digraphs. L0ind 0GxG x, 1ind 0GxG x, 00HxHindx, 10HxHindx . and If 1xG ind ,ind0,axaind x th end 0. Lin,ax et ',,,jaxa x then we have '1xH and .jaa Np 11 1:GHow we define a ma by ',1xx1. xGObviously, 1 is injIf ective. '1,yH ethe exists a vex ,ay of pn therrteosi-tive iin mOGndegree  such that '.ay Hence ,,ay'1yy and 1 is also surjectiNow that 1ve. we assume,xyG, and there is a directed edge from x to y. Let '',,11xxyyby defini-tion we have x ax', and ,a,ay ',.ay We know that there is a directed edge from,ax to ,,ay then there is also a directed edge from  to ',ax',ay since  preserves arrows. So there a dd edge from 'is also irectex and 'y. We showed that 1 preserves arrows. For any 1yG, let 10 is a directed edge from to ,there is a directed ed ge from to ,xGx yxGx y yd the above union is a disjoin union since each 00thereEyEythen Anve100yGGE trtex has outdegree 1. If '1yy, by Lemma 4.4 we have   01''01', ind,aym EyEyaym EyEy indeg Copyright © 2011 SciRes. OJDM G. X. DENG ET AL. 106 and'11Ey Ey maps 1Ey since 1 into . Then we also have '1Ey'.00Ey Nowe ne a map Ey wcan defi0 from to 0 0GH such that for any 0xyE,  0.0 1xEy Fily we can define :GHnal  iiaaaGfoif , r 0,1.i It is easy to show that  is bijective. Now we prove that  preserve arrows. Suppose ,xyG needand therdge from x to y. We e is a directed eonlyto treat the case when 0xG and y1G. Le't 1yyy. By the construction of 0 we  '00,see that xxEy so there is also a arrow from x to y. It is easy to show that the number of direcis equal to the number of dicted edges ofte d edges of G H. Thus re is anorphism. Lemma 4.5 is proved.□ 5. The Main Theorem o begi n wi isomTth, we pr o ve the fol l owing lemma. component ofLemma 5.1 Let E be the 64 ,4Gq be another phic to F. lid. containing the vertex 0 where q is odd and F is where prcomponent of 64 ,4Gq. Then E is not isomorAnd the similar result for 32,2Gq is also vaProof. We only prove the case for 64 ,4Gq, the proof for 32Gsimilar and we omit the details. Assume that 1ireiiqpeach ip is an odd ,2q ime, and 2ie if ,is 1ie if .sirve Let 0 or C and iC the components of 64,4G and containing the rtex 1, and letieiGp,4 ,  and 1, 2,,ir n10.rECC C of F > 1, then F is not isomorhic to hat the cycle length orespectively. The 00 If the cycle length pE. Suppose tf F is 1, by L emma 4.1 12 ,rFCFF F where Fi is a component of cycle length 1 contained in ,4ieiGp . By Lemma 3.1 we can write 011,rrFCC C wher 0 or 1. By computations we know that e By Lemma .3 there exists i16, such 018.MC MC1iuthat 0i3iuiMCp or if 2,iuip or 4iuip1 ,is 01i if .MCsir And by Lemma 3.2 1,4 2 or 4. for any 1igcd11ieiiMCppi hus 6 ,siiMC .r T001116 1riiME MC1() iriiMF MCMC .Now if (),MEMF0 we have and if 12 0s , 0 then all i0, .EF If 01, then 1sr and 2gcd 1,rpk. But in th case is010132.iiiriiC pFC C 1rr101111,||ieirECCTherefore we have MEMF or EF, E is not isomorphic to Fed.Theorem 5.1 (Main Theorem) Let and n. Lemma 5.1 is prov□ 2k  2,mq where and q is odd1m . Then k is ,Gnsymmetric if and only if 2,mGk is symmetric. ove thProof. By Lemma 4.2 we only need to pre ne-cessity. The case 1m is trivial, so we may ass 2m. Lbe the component of umethat et 0C  containing the vertex 0,be the compon2,mGkent of and 1C 2,mk containing the vertex 1. Let G00hhC and 11hhC. We cthat laim 2k and 01.hh Other-wise ume firstly that k is odd or 01.hh Incases we have we ass both 01222,,mhmGkO and if 02,hmxGk 0,xand then 012ind2.hmkmx By Lemma 4.3 0,hGnk is alsoetric and symm ,m0,hGnk G Let H02,hk Gqks0.hwhere each 0,,hiiiGqk m 1iHis a connect cent such that omponijHH if any ifd onl ,ij and ijMHMH for .ij We choossuch cane an l that lm is odd and 2jm if ,jlince 0,hGqk is not symmetric. sThen 012, lhmik m is alsiiHG o symmetric. Let 0,,hmlEkH by Lemma 4.1 E connected en22Gpon tis a com of 02,hmi since 1liimGk H022,hmGk is a co1. Let F be another com-mnent of ponent of cycle length po1.iiimH Suppose that by Lemma 4.1 again F is a component of ,i02,hml,EF GkKH where K i0,hmk and 1ils a component of. 2G But we have 121 2mlm liMEMO HMHMKMHMF Copyright © 2011 SciRes. OJDM G. X. DENG ET AL. Copyright © 2011 SciRes. OJDM 107where the equality holds if and only if 12mMK  G. Chartrand and L. LesnidEdition),” Chapman Hall, London, 1996k, “Graphs and Digraphs (3rd . dulo a Prime,” and  ,ilMHMH which implies 022, .hmKG k But now we have 022,hmiFGkOHOHH a. nd  Wun-Seng Chou and Igor E. Shparlinski, “On the Cycle Structure of Repeated Exponentiation Mo1122mmliHence liHH by Lemma 4.5We show that there , il. are exactly ml components contained in02,hmGklmH 1iiiIt is contrary to th0hwhich are isomorphic to E. e fact that is symmetric. have Journal of Number Theory, Vol.107, No. 2, 2004, pp. 345-356. doi:10.1016/j.jnt.2004.04.005  Joe Kramer-Miller, “Structural Properties of Power Di-graphs Mudulo n,” Manuscript. lmH  M. Krizek, F. Lucas and L. Somer, “17 Lectures on the Femat Numbers, from Number12,miiiGk  Theory to Geometry,” Quart, Vol. 34, 1996, pp. the Theory of Numbers,” 5th Edition, 148, No. 1-23, Springer, New York, 2001.  C. Lucheta, E. Miller and C. Reiter, “Digraphs from Pow-ers Modulo p,” Fibonacci Now we2,k if 01,hhnsider coWd Using the same arguments we can show that 226-239.  I. Niven, H. S. Zuckerman and H. L. Montgomery, “An Introduction to 111122, 2,2,hhhmmmGkGkGk. e have 11122, mhmGkO anMJohn Wiley & Sons, New York, 1991.  T. D. Rogers, “The Graph of the Square Mapping on the Prime Fields,” Discrete Mathematics, Vol.112,2,.hhmmGkMGk 211996, pp. 317-324. doi:10.1016/0012-365X(94)00250-M  L. Somer and M. Krizek, “On a Connection of Number Theory with Graph Theory,” Czechoslovak Mathematic 1,hGnk , we have is not symmetric. Hence then for any vm if a is evelies that is 01.hhh ert If 1,hex a0mkan and ,od. It imet2,mG k1moda122 .mGkO d2is odpsymm ric in this case. 2km2,mGkJournal, Vol. 54, No. 2, 2004, pp. 465-485. doi:10.1023/B:CMAJ.0000042385.93571.58  L. Somer and M. Krizek, “Structure of Digated with Quadratic Congruences with if a 2,mrphs Associ-Composite If 1,h then 3.m Assume that 2rk have (3.1) and (3.2), by orem ha, then wethe proof of The 3.1 (4, 2). Thenis comd by rem 3.1. k be two positive integers is symmetric if and only if rem No. 1, 2Moduli,” Discrete Mathematics, Vol. 306, No. 18, 2006, pp. 2174-2185. doi:10.1016/j.disc.2005.12.026  L. Somer and M. Krizek, “On Semiregular Digraphs of the Congruence xk  y(mod n),” Commentationweve (= (5, 4), (6, 4), (5, 2) or the proof Lemma 5.1 and TheoCorollary 5.1 Let n,and 2,1mnm. Then G k = 1 m, k) plete □ es Mathe-ud. KÄozl, Vol. 8, 1992, pp. 71-91. ematics, Vol. maticae Universitatis Carolinae, Vol. 48, No. 1, 2007, pp. 41-58.  L. Szalay, “A Discrete Iteration in Number Theory,” BDTF T,nk one oor k, m satisfyf (i) - (v) in Theo 3.1. 6. References  L. Somer and M. Krizek, “On Symmetric Digrphs of the Congruence xk  y (mod n),” Discrete Math309, No. 8, 2009, pp. 1999-2009. doi:10.1016/j.disc.2008.04.009  B. Wilson, “Power Digraphs MQuart, Vol. 36, 1998, pp. 229-239. W. Carlip and M. Mincheva, “Symmetry of Iteration Digraphs,” Czechoslovak Mathematic Journal, Vol. 58, 008, pp. 131-145. doi:10.1007/s10587-008-0009-8 odulo n,” Fibonacci