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)
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
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 [12], L. Szalay showed that is symmetric if
or . In [1], 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 [13].

,2Gn

8
5r


2mod4n
k

4modn
3r

2,2
r
Gp
4
Theorem 1.1 ([13] Theorem 5.1) Let 12 nnn

,
where 12
and . Suppose that
1, where . Then is symmetric if
one of the following conditions holds:
1, 1nn
mm12
gcd ()1nn 

,Gnk
2n1
i) and
2, 2,mk 1 2;
mk 
ii) and 3, 2,mk 2 2;
mk 
iii) and 4m2k
In this paper we prove that if is symmetric,
where and

,Gnk

2km 2n, 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,
m
Gk

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:







  
12
2
1
12
1
11,
21,
42,
22 if 3,
1 if is odd prime,
lcm ,,,
ir
kk
kk
reee e
ir
i
k
ppp pan
ppp














p 






where pi are distinc primes.
The following theorem generalizes the well-known
Euler’s theorem which says that if and
only if


1mod
n
an





gcd ,1an

.
Theorem 2.1 (Camichael). Let Then ,.ana
 n 



1mod n
ord g
if and only if . Moreover, there
exists an integer g such that where
denotes the multiplicative order of g modulo n.

1an 
n
ordg 
gcd ,

,n 
n
For 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

indk
na


,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



k
1
Gn,

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 nk
Gn 2,Gn

,Gn
. A

,

2
It 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.

k
nd

,Gnk
1t


,Gnk
Lemma 3.1 ([13] Corollary 6.4) Let be a fixed
integer. Then any two components in con-
taining t-cycle are isomorphic. 1
Definition 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 i
k
c iongruent modulo n to a cycle
vertex in

,Gnk if C is a component of

,Gnk
c

s


,Gnk,
e

suhC 
we de
in ind
fin

1,Gnk

d
2
i

.hc p
ei
i
kk
n
p
cC
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

p
i
Lemma 3.2 ([14]) Let be the prime
1i
r
i
e
i
n


factorization of n. Let a be a vertex of positive indegree
in . Then

11
gcd
rr
ii






, ,
i
e
i
apak
where

 if 2k and 8i
e
i
p, and 1
i



,
ek
other-
wise.
Lemma 3.3 ([11] Theorem 3.2) Let p be a prime. Let
a be a vertex of positive indegree in , and
assume that 2
Gp
l
p
ind e
p
2
k
and . Then for some
positive integer t and 0alkt
l
k


 
1gcd , kt
ke
ap p 


where

 if 2,2pk and and 3,el 1


otherwise.
Lemma 3.4 ([13] Lemma 3.2) Let p be a prime and e,
k be two positive integers. Then

ind 0.
e
e
e
kk
pp




Lemma 3.5 Let p be a prime and be
two positive integers. Let h be the positive integer such
2,e2k
that . Then
1
ke
 hh
k



2,
e
hhGpk

,
e
pGpk
.
Proof. It is clear that and
2


hp

And
 
,.
e
p k
2
hG


0mod
k
pp
ie
v
if and only if
This proves the Lemma.□ .e
i
k
Lemma 3.6 Let p be a prime and be two
positive integers. Let ,ek2

e
pu 

where u is the maxi-
mal divisor of relatively prime to k. If G is the
component of containing 1, then

e
p 

,
e
Gp


k



min :i hC ivk
Proof. Let


min :.
i
hivk Then there exists a di-
visor d of v such that d is not a divisor of 1h k

. By
Theorem 2.1 there exists a vertex

,
e
g
Gpk such
that .
e
p
ord guv

Let

mod
uv e
d
ag p

. Then
e
p
ord a
d

and 1h
k
a

is not congruent modulo to 1, but
e
p


od1m
k
a
he
p. We have by the
definition of height functio n.
 
hC hh

a
Conversely if ,aC

then there exists such
that
1j


,
ke
1mod
jap then .
e
p
orda k Bu t ,
e
p
orda uv hence
.
e
p
orda v And


1mod .
h
k
ae p 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,
m
Gkis 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


2
22
m


. We first suppose that is sym-
metric. Let 0 and 1 be the components of

2,
mkG
C C


2,
m
Gk 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 1
C are 1, by the assump-
tions and Lemma 3.1 we must have, thus
C

2,
m
Gk
0
CC

1
C




01
hChhC
1h. If

, then k and m



gcd 1nd
2,ki2m


02d1m in

, where 1

 if k is odd, and 2

 if
2k. We must have 2 2mk
.
If 2k

, then 1 is a cycle, however is not a
cycle. Hence we may assume that
C0 C
2,kr1
r and
2h. We have



2
2m
1min:i
hhCi k by
Lemma 3.6. It implies that


12rhm rh. (3.1)
Since


0
hhC, by Lemma 3.5 we have
1. h
kmk
 h
(3.2)
Combining (3.1) and (3.2), we obtain


11
21
rh h
kmrh1,




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,2G By computations we know that both and


32,4G are symmetric. For and

32,2G



,464G,

105 G. 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 ,

2
32
ind 48

16
C

2
32
ind 4a4
64
ind 16


a 8
4
64
ind

.
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

kG
G
4. Properties of Digraphs Product
Given two digraphs 1 and 2 G. Let 12 G be the
digraph whose vertices are the ordered pairs
G


12
,,aa
where i
and there is a directed edge from
i
aG


12
,aa
b

12 1,nn
to if there is a directed edge from i to i
for In [13] L. Somer and M. Krizek proved the
following fact: Let where

12
,bb
1,2.ia

gcd ,
12
nnn

then 12
And the canonical
isomorphism is given by where

Gnk

,,nk

Gnk


,.

12
,aaa
Ga

In general we have

mod ,
ii
an

Gnk
r
i
i
n



12
gcd ,nn
1,2.

,,k
i

,r
ee
r
k Gp
nnn

,k
12
12
e
Gp,
p
Gp
if 1 is the prime factorization of n. We need
this fact and the following lemma.
i
e
Lemma 4.1 ([4] Lemma 3.1) Let 12 where
. Let i
C be a component of 1


,
i
Gnk
12
.
And the cycle length of i C is i. Then tCC

is a
subdigraph of Gn consisting of com-
ponents, each having cycles of length .

,k

 
12
gcd ,tt

12
lcm ,tt

12
gcd ,nn


1Lemma 4.2 Let 12 where nnn

. If
is symmetric, then is symmetric.

1,Gnk
Gn

Gn

12
k Gn


,k
(,) k
Proof. It follows immediately from Lemma 4.1 and
the fact .□

,,k
k

Gn

,GnLemma 4.3 If is symmetric, then


,r Gnk
is also symmetric for any . 1r

,Gnk  Proof. Assume that has 2m components, say,
12 2 and for each there exists
an isomorphism
,,,m CC C,1, 2,,im
i

of digraphs:
:.
mii i
CC




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

,r Gnk mo
u
k
x
zn, which
implies that x, y are in the same component of

mod
v
k
yz

n


,Gnk

.
It follows that if D is a component of , then
there exists a such that

,r Gnk

2,j

2m1, ,
j
DC.
Let 1
1
s
1
j
i and where CD2
1
s
mj
iE


1
C

j
D,
1 and , are components of
. If
1, 2,,js

,r Gnk l
E
1
2
s1, 2,,l
,
x
yC and

mod ,
r
k
x
yn

1mod
k
 then there
exist such that
12
,,yy,
r
yy

,
x
yn and


1mo d
k
ii .
y
y

n
So

1

k
 
1
mod
x
yn 
and

k
i
y
 
1


11
mo
i

d ,
y
n 

 we get

11
r
k
 
mo d
x
yn  
and 1

still preserves arrows e consider 1 C and
1m
C
if w

as subdigraphf s o


,r k
12
Gn
It fo
s
s llows that

and 1

is still an isomor-
phism if we consid1 C as subdigraphs of er 1 C and m


,r Gnk . Hence


Gn is asymmetric. Lemma
ved.□
Let G be adigra
,r kls
h. Let
o
4.3 is proG d genote the number of
vertices in G, and let

 
ax .
cG
m
M
Gindc


Lemma 4.4 Let G dand Ho digraphs, an be tw ,aG

.Hb

Then



  
ind ,indind,abab


HMG






,
M
GMH and GHGH .
Proof
of th
ve
. It follows imhmediately from te definitions.□
The following lemma is the key lemma for the prf oo
he digraph whose set of
e main result of this paper.
Lemma 4.5 Let m O denote t
rtices is


011
, ,
m
aaa

 and there is a directed
edge from ,a
i
a to
j
a if
ph and on o ly if 0j
aaa. Let G
and H be twdigras such that all vertices and H
have outdegree 1. Then mm OGOH if and only if
GH.
in G
:mm OGOH

 
et
Proof. Assume that is an iso-
morphism of digraphs. L



0ind 0GxG x

,


1ind 0GxG x,



00HxHindx

,


10HxHindx .
and

If 1
x
G




 
ind ,ind0,axaind x th en




d 0. Lin  ,ax et





'
,,,
j
axa x   then we have
'1
x
H and .
j
aa

Np 11 1 :GHow we define a ma


by


',
1
x
x1. 
x
G

Obviously, 1

is inj
If ective. '1,
y
H ethe exists a vex

,ay of pn therrteosi-
tive iin m OG ndegree

such that
 


'.ay
 
Hence ,,ay


'
1yy


and 1

is also surjecti
Now that 1
ve.
we assume,
x
yG, and there is a directed
edge from x to y. Let


''
,,
11
x
xyy  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 irecte
x
and '
y
. We
showed that 1

preserves arrows.
For any 1 yG

, let




 
10
is a directed edge from to ,
there is a directed ed ge from to ,
xGx y
xGx y


y
d the above union is a disjoin union since each
00
thereEy
Ey
then
An
ve

1
00
yG
GE


t
rtex has outdegree 1. If

'
1yy
 , by Lemma 4.4 we
have


  


   

01
''
01
'
,
ind,
aym EyEy
aym EyEy


indeg

G. X. DENG ET AL.
106
and


'
11
Ey Ey maps


1
Ey since 1

into
. Then we also have

'
1
Ey


'.
00
Ey Nowe
ne a map Ey w can defi0

from to 0 0 G
H
such that for
any

0
x
y
E, 
 


0. 0 1
x
Ey
Fily we can define :GH

nal


 
ii
aaaG  
fo
if ,
r 0,1.i It is easy to show that

is bijective.
Now we prove that

preserve arrows. Suppose
,
x
yG
needand therdge from x to y. We e is a directed e onlyto treat the case when 0
x
G and y1 G

.
Le

'
t

1
yyy  . By the construction of 0

we
 

'
00
, see that
x
xEy   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 of
te
d edges of G H. Thus re

is
anorphism. Lemma 4.5 is proved.□
5. The Main Theorem
o begi n wi
isom
Tth, 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
pr
component of

64 ,4Gq. Then E is not isomor
An

d the similar result for 32,2Gq is also va
Proof. We only prove the case for

64 ,4Gq, the
proof for

32Gsimilar and we omit the details.
Assume that 1i
re
i
i
qp

each i p is an odd
,2q
ime, and 2
i
e if ,is 1
i
e if .
s
ir
ve
Let
0 or C and i
C the components of

64,4G and containing the rtex
1, and let

i
e
i
Gp

,4 ,

and
1, 2,,ir n
10
.
r
ECC C
of F > 1, then F is not isomorhic to
hat the cycle length o
respectively. The
00 
If the cycle length p
E. Suppose tf F is 1, by L emma 4.1
12 , r
F
CFF F

where Fi is a component of cycle length 1 contained in

,4
i
e
i
Gp . By Lemma 3.1 we can write
01
1,
r
r
F
CC C


wher 0 or 1. By computations we know that

e
By Lemma .3 there exists
i


16,
such
01
8.MC MC
1
i
uthat

0
i
3
i
u
i
M
Cp or if 2,
i
u
i
p or 4i
u
i
p1

,is

01
i if .

MC
s
ir And by Lemma 3.2

1,4 2 or 4. for any 1i

gcd


11i
e ii
MCpp 
i

hus

6 ,
s
i
i
MC


.r T


00
11
16 1
r
i
i
ME MC





1
() i
ri
i
MF MCMC



 .
Now if


(),
M
EMF
0 we have
and if 12 0
s
 ,
0

 then all i0,

 .EF If 01, then 
1
s
r

 and


2gcd 1,
r
pk.

 But in th case is

0
1
0
1
32
.
i
ii
ri
i
C p
FC C



1rr1
0
11
11
,
||
i
e
i
r
EC
C






Therefore we have


M
EMF 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 ,Gn
symmetric if and only if


2,
m
Gk 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 ume that et 0 C


containing the vertex 0,be the compon2,
m
Gk
ent of and 1
C


2,
mk
containing the vertex 1. Let G


00
hhC and


11
hhC. We cthat laim 2k and 01 .hh Other-
wise ume firstly that k is odd or 01
.hh In
cases we have
we ass both


01
22
2,,m
h
m
GkO

 and if


0
2,h
m
x
Gk
0,x

and then

01
2
ind2.
h
m
km
x 
By Lemma 4.3


0
,h Gnk is alsoetric and symm






,
m
0
,
h
Gnk G Let
H
0
2,
h
k Gqk
s
0
.
h
where each

0
,,
hii
i
Gqk m
1
i
H
is a connect cent such that ompon
ij
H
H if any ifd onl ,ij

and



ij
M
HMH
for .ij

We choossuch cane an l that l m is odd and
2
j
m if ,jlince

0
,h Gqk is not symmetric. s
Then




01
2, l
h m
i
k m

 is als
ii
HG o symmetric. Let


0
,,
h
ml
EkH by Lemma 4.1 E connected
en
22G
pon t
is a
com of




0
2,h
mi
since
1
l
i
i mGk H


0
22,h
m
Gk
is a co1. Let F be another com-m
nent of
ponent of cycle length
po




1.
ii
imH

 Suppose that
by Lemma 4.1 again F is a component of ,
i
0
2,h
ml
,EF
Gk
K
H

where K i

0
,h
mk and 1il
s a component of.

2G


But we have

 1
2
1
2
ml
m

 

l
i
M
EMO H
MH
M
KMH
MF







G. X. DENG ET AL.
107
where the equality holds if and only if

1
2m MK

 [2] G. Chartrand and L. Lesnid
Edition),” Chapman Hall, London, 1996
k, “Graphs and Digraphs (3rd
.
dulo a Prime,”
and
 
,
il
M
HMH which implies


0
22, .
h
m
KG k
But now we have

0
22,h
mi
F
Gk
OHOH

H a
.
nd [3] Wun-Seng Chou and Igor E. Shparlinski, “On the Cycle
Structure of Repeated Exponentiation Mo
11
22
mm
li

Hence li
H
H by Lemma 4.5We show that there , il.
are exactly ml components contained in


0
2,h
m
Gk
lmH


1ii i

It is contrary to th

0
h

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
[4] Joe Kramer-Miller, “Structural Properties of Power Di-
graphs Mudulo n,” Manuscript.
lmH [5] M. Krizek, F. Lucas and L. Somer, “17 Lectures on the
Femat Numbers, from Number

1
2,
mii
i
Gk 
Theory to Geometry,”
Quart, Vol. 34, 1996, pp.
the Theory of Numbers,” 5th Edition,
148, No. 1-23,
Springer, New York, 2001.
[6] 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.
[7] I. Niven, H. S. Zuckerman and H. L. Montgomery, “An
Introduction to

111
12
2, 2,2,
hhh
mmm
GkGkGk.
e have

11
12
2, m
h m
GkO

 an

M
John Wiley & Sons, New York, 1991.
[8] T. D. Rogers, “The Graph of the Square Mapping on the
Prime Fields,” Discrete Mathematics, Vol.




11
2,2,.
hh mm
GkMGk
21
1996, pp. 317-324. doi:10.1016/0012-365X(94)00250-M
[9] L. Somer and M. Krizek, “On a Connection of Number
Theory with Graph Theory,” Czechoslovak Mathematic


1
,h Gnk
, we have
is not symmetric. Hence
then for any v

m
if a is eve
lies that is
01.hhh
ert If 1,hex a

0m
k
an and
,
o
d. It im
et

2,
m
G k
1moda

1
2
2 .
m
GkO


d2
is odp
symm ric in this case.

2
km

2,
m
Gk
Journal, Vol. 54, No. 2, 2004, pp. 465-485.
doi:10.1023/B:CMAJ.0000042385.93571.58
[10] L. Somer and M. Krizek, “Structure of Dig
ated 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 we
the proof of The 3.1
(4, 2). Then
is comd by rem 3.1.
k be two positive integers

is symmetric if and only if
rem
No. 1, 2
Moduli,” Discrete Mathematics, Vol. 306, No. 18, 2006,
pp. 2174-2185. doi:10.1016/j.disc.2005.12.026
[11] L. Somer and M. Krizek, “On Semiregular Digraphs of
the Congruence xk  y(mod n),” Commentation
we
ve (= (5, 4), (6, 4), (5, 2) or the proof
Lemma 5.1 and Theo
Corollary 5.1 Let n,and
2,1
mnm. 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.
[12] L. Szalay, “A Discrete Iteration in Number Theory,”
BDTF T
,nk
one oor k, m satisfyf (i) - (v) in Theo 3.1.
6. References
[1]
[13] L. Somer and M. Krizek, “On Symmetric Digrphs of the
Congruence xk  y (mod n),” Discrete Math
309, No. 8, 2009, pp. 1999-2009.
doi:10.1016/j.disc.2008.04.009
[14] B. Wilson, “Power Digraphs M
Quart, 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