
In this work, we incorporate modular arithmetic and discuss a special class of graphs based on power functions in a given modulus, called power digraphs. In power digraphs, the study of cyclic structures and enumeration of components is a difficult task. In this manuscript, we attempt to solve the problem for pth power congruences over different classes of residues, where p is an odd prime. For any positive integer m, we build a digraph G(p,m) whose vertex set is Zm={0,1,2,3,...,m−1} and there will be a directed edge from vertices u∈Zm to v∈Zm if and only if up≡v(modm). We study the structures of G(p,m). For the classes of numbers 2r and pr where r∈Z+, we classify cyclic vertices and enumerate components of G(p,m). Additionally, we investigate two induced subdigraphs of G(p,m) whose vertices are coprime to m and not coprime to m, respectively. Finally, we characterize regularity and semiregularity of G(p,m) and establish some necessary conditions for cyclicity of G(p,m).
Citation: M. Haris Mateen, Muhammad Khalid Mahmmod, Dilshad Alghazzawi, Jia-Bao Liu. Structures of power digraphs over the congruence equation xp≡y(modm) and enumerations[J]. AIMS Mathematics, 2021, 6(5): 4581-4596. doi: 10.3934/math.2021270
[1] | Nuttawoot Nupo, Sayan Panma . Certain structural properties for Cayley regularity graphs of semigroups and their theoretical applications. AIMS Mathematics, 2023, 8(7): 16228-16239. doi: 10.3934/math.2023830 |
[2] | Zhi-Hong Sun . Supercongruences involving Apéry-like numbers and binomial coefficients. AIMS Mathematics, 2022, 7(2): 2729-2781. doi: 10.3934/math.2022153 |
[3] | Sufyan Asif, Muhammad Khalid Mahmood, Amal S. Alali, Abdullah A. Zaagan . Structures and applications of graphs arising from congruences over moduli. AIMS Mathematics, 2024, 9(8): 21786-21798. doi: 10.3934/math.20241059 |
[4] | Nuttawoot Nupo, Chollawat Pookpienlert . Fractional domination and fractional total domination on Cayley digraphs of transformation semigroups with fixed sets. AIMS Mathematics, 2024, 9(6): 14558-14573. doi: 10.3934/math.2024708 |
[5] | Changsheng Luo, Jiagui Luo . Complete solutions of the simultaneous Pell equations $ (a^2+1)y^2-x^2 = y^2-bz^2 = 1 $. AIMS Mathematics, 2021, 6(9): 9919-9938. doi: 10.3934/math.2021577 |
[6] | Cencen Dou, Jiagui Luo . Complete solutions of the simultaneous Pell's equations $ (a^2+2)x^2-y^2 = 2 $ and $ x^2-bz^2 = 1 $. AIMS Mathematics, 2023, 8(8): 19353-19373. doi: 10.3934/math.2023987 |
[7] | Shujie Zhou, Li Chen . On the sixth power mean values of a generalized two-term exponential sums. AIMS Mathematics, 2023, 8(11): 28105-28119. doi: 10.3934/math.20231438 |
[8] | Cheng Feng, Jiagui Luo . On the exponential Diophantine equation $ \left(\frac{q^{2l}-p^{2k}}{2}n\right)^x+(p^kq^ln)^y = \left(\frac{q^{2l}+p^{2k}}{2}n\right)^z $. AIMS Mathematics, 2022, 7(5): 8609-8621. doi: 10.3934/math.2022481 |
[9] | Yahui Yu, Jiayuan Hu . On the generalized Ramanujan-Nagell equation $ x^2+(2k-1)^y = k^z $ with $ k\equiv 3 $ (mod 4). AIMS Mathematics, 2021, 6(10): 10596-10601. doi: 10.3934/math.2021615 |
[10] | Jizhen Yang, Yunpeng Wang . Congruences involving generalized Catalan numbers and Bernoulli numbers. AIMS Mathematics, 2023, 8(10): 24331-24344. doi: 10.3934/math.20231240 |
In this work, we incorporate modular arithmetic and discuss a special class of graphs based on power functions in a given modulus, called power digraphs. In power digraphs, the study of cyclic structures and enumeration of components is a difficult task. In this manuscript, we attempt to solve the problem for pth power congruences over different classes of residues, where p is an odd prime. For any positive integer m, we build a digraph G(p,m) whose vertex set is Zm={0,1,2,3,...,m−1} and there will be a directed edge from vertices u∈Zm to v∈Zm if and only if up≡v(modm). We study the structures of G(p,m). For the classes of numbers 2r and pr where r∈Z+, we classify cyclic vertices and enumerate components of G(p,m). Additionally, we investigate two induced subdigraphs of G(p,m) whose vertices are coprime to m and not coprime to m, respectively. Finally, we characterize regularity and semiregularity of G(p,m) and establish some necessary conditions for cyclicity of G(p,m).
In fields such as data structures, computer algorithms, data encryption, security, and networking, computer science relies heavily on graph theory. For instance, designs of a database, routing problems, and networking based on the key ideas of graph theory, namely cycles and trees. Many computer security algorithms and ciphers are similarly based on modular arithmetic from number theory. In these areas, a strong mathematical background and a clear understanding of modular arithmetic, graph theory and algorithms needs to be developed to enjoy the subject. Computer software or a program without adequate knowledge of mathematics is often difficult to understand. The entire structure of an algorithm can be understood through a flow chart or its graph (or digraph). Graphs (or digraphs) are thus much more useful for a better understanding of structurally dependent algorithms and/or outputs. Digraphs based on congruence equations are a primary interest in the field of discrete mathematics for number theorists and computer scientists. Power digraphs have a broad range of applications that are easily recognizable in almost every field and presented with the basic properties of integers. For instance, if a typical power digraph is described and its loops are discovered. Then, instead of ordinary integers, one can consider these vertices (that is, loops) in forming a new cipher. Obviously, it would be difficult to decode this type of cipher unless one knows the correct mapping and its reverse mapping (if possible). In fact, a typical corresponding congruence must be solved to decode such a produced cipher. The problem of factorization in computer science is a very difficult problem for large integers. For such an integer, a digraph which assigns a component to its divisor can always be described. The divisor number can therefore be enumerated as the number of components that are non-isomorphic. The required integer may therefore be written canonically. Let's define our power digraph before proceeding further.
Let m>0 be any integer and ¯r denotes the set of all integers which leave remainder r under modulo m, also referred as a residue class of m. Thus, {¯0,¯1,¯2,¯3,…,¯m−1} is the set of all residue classes of m. This set is called a complete residue system (CRS). We construct a digraph G(p,m) on this set of complete residue classes of m and build a directed edge from u to v if and only if up≡v(modm). The vertices u1,u2,...,us will form a cycle of length s if
up1≡u2(modm),up2≡u3(modm),⋮ups≡u1(modm). | (1.1) |
The indegree of a vertex a is the count of edges incident with it and the number of edges leaving from a vertex a is called outdegree of a. The indegree and outdegree are labeled as indeg(a) and outdeg(a), respectively. The cycles of length one are called fixed points of the map f(u)=up and cycles of length q are called q-cycles. A maximal connected simple subetaaph of the corresponding digraph G(p,m) is termed as a component. Since every integer lies in a unique residue class of m, so its outdegree must be one.
If indegrees and outdegrees of all vertices are the same then the corresponding digraph is called a regular digraph. In this case, a digraph is regular if the indegree of every vertex is one (since the outdegree of each vertex is already one). If the indegrees of all vertices are either a positive integer d or 0, we then call it a semiregular digraph. Let G1(p,m) and G2(p,m) denote the subdigraphs induced by the proposed digraph G(p,m) over the set of vertices which are either coprime to m or not, respectively. Note that the digraphs G1(p,m) and G2(p,m) are disjoint and their union is G(p,m). The digraph G(11,17) is depicted in Figure 1.
Power digraphs have been of great interest for the last few decades. In 1967, Bryant [1] employed quadratic digraphs and enumerated isomorphic subetaoups of a finite group. Szalay [2] investigated some interesting properties of power digraphs based on congruences and established the existence of cycles in components. In 1996, Rogers [3] and Somer et al. [4] investigated the structures of quadratic maps and explored a few results on fixed points, existence of cycles and few decomposition of components. Mahmood and Ahmad [5] established many results for k-array digraphs and completely described an enumeration of squares of 2k using modular arithmetic for any intger k. Aslam and Mahmood introduced and investigated simple graphs over exponential congruences and characterized all cycles and components completely in [6]. Yangjiang et al. [7] and Somer et al. [8] introduced and investigated the symmetric structures (isomorphic components) of such digraphs. For a fixed k, many useful results on loops, cycles, components and symmetry of power digraphs for the congruence equation xk≡y(modm) have been proposed and proved in [9,10,11,12,13]. Akbari [14] established a relation between edge chromatic number of G(R) with the maximum degree of G(R), where G(R) denotes the zero-divisor graph over of a finite commutative ring R. Wei et al. and Rezaei et al. [15,16,17] discussed graphs based on quadratic and cubic congruences over finite integral rings. Carlip and Mincheva [18] defined an M-ordered symmetric digraph of G based on M-size subsets, each containing M-isomorphic components. Deng and Yuan [19] investigated symmetric digraphs for a fixed power modulo n. Meemark and Wiroonsri [20,21] discussed the structure of G(R,k), where R is the quotient ring of polynomials over finite fields and k is the modulus. Mahmood and Ali [22,23,29] investigated new numbers on euler totient, super euler function and labeling algorithm on several classes of graphs with application. Alolaiyan et al. [24] studied non-conjugate graphs associated with finite groups. Portilla et al. [25] generalize the classical definition of Gromov hyperbolicity to the context of directed graphs. It is worth mentioning that the problem of enumeration of components of power digraphs is still open. In fact, previously all structures have been established for a fixed power k. In this piece of work, we generalize the structures of these digraphs when power is an odd prime p. That is, we incorporate the congruence, xk≡y(modm).
We organize our paper as follows. In Section 1, we introduce our digraph with some important definitions and also provide some new results on fixed points. In Section 2, we prove some results that enumerate cyclic vertices as well as the existence of a t-cycle in G(p,m). Then, we define two subdigraphs G1(p,m) and G2(p,m). Then after, we elaborate cyclic structures and enumerate components of these subdigraphs for m=2r and m=pr for all positive integers r. Finally, we prove that the digraph G1(p,m) consists of p−1 isomorphic trees where as G2(p,m) is a tree with root at 0 with indeg(0)=pk−⌈kp⌉. In Section 3, we characterize regularity and semiregularity of G1(p,m). We need the following definitions for use in sequel.
Definition 1.1. [26] Euler totient function counts the positive integers up to a given integer m that are relatively prime to m. It is written using the Greek letter phi as ϕ(m), also called Euler phi function.
Definition 1.2. [26] Let m>0 be any integer. For a prime p, the Carmichael λ-function (or λ(m)) is defined as follows: λ(1)=1=ϕ(1),λ(2)=1=ϕ(2),λ(4)=2=ϕ(4),λ(2k)=12ϕ(2k),k≥3, and λ(pk)=ϕ(pk),k≥1.
Theorem 1.3. [27] (Carmichael). Let a,m∈N. Then aλ(m)≡1(modm) if and only if gcd(a,m)=1. Here, gcd(a,m) is the greatest common divisor of a and m.
Theorem 1.4. The Chinese Remainder Theorem (for detail see page 230, Fact 4 of [28])
Define
η1={0ifb=0,11ifb≥2, |
and
η2={0ifb<31ifb≥3, |
If gcd(2b,u)=1, then the number of solutions for the congruence ut≡a(mod2b) is either 0 or (gcd(2,t))η1(gcd(2b−2,t))η2.
The following inequality can easily be proved using mathematical induction.
Lemma 1.5. For t≥2,t≤β(t−1),β=2,3,4,….
Lemma 1.6. For a prime p of the type p≡3(mod4),k≥4, then, 1,2k−1±1,2k−1 are fixed points in G1(p,2k) and 0 is the only fixed point in G2(p,2k).
Proof. For k≥4,α=1+2k−1 is a fixed point if αp≡α(mod2k). For this, note that
(1+2k−1)p=1+p2k−1+p∑β=2(pβ)2β(k−1). | (1.2) |
As k≥4, Lemma 1.5 invokes, k≤β(k−1),β=2,3,4,…,n which further gives 2k|2β(k−1). But then,
p∑β=2(pβ)2β(k−1)≡0(mod2k). | (1.3) |
Also, p=4t+3 for some integer t=0,1,2,…. Using the expression of p together with Eqs (1.2) and (1.3), we get
(1+2k−1)p≡1+(3+22t)2k−1(mod2k)≡1+(1+2+22t)2k−1(mod2k)≡1+(2k−1+2k+2k+1)(mod2k)≡1+2k−1(mod2k). |
Similarly, we can follow the same procedure to prove the remaining fixed points. Also by Theorem 1.4, the number of solutions of up−1≡1(mod2b)with2∤u is (gcd(2,p−1))η1(gcd(2b−2,p−1))η2. Note that, in our case, η1=η2=1,withb≥3. As p≡3(mod4) can also be written as p−1=2(1+2t),t∈Z+. Hence, we get gcd(2,2(1+2t))⋅gcd(2b−2,2(1+2t))=2⋅2=4. This shows that there are exactly four fixed points.
Proposition 1.7. The graph G1(p,2k) has 8 fixed points which are 1,±1+2k−1,±1+2k−2,2k−1,−(2k−2±1)+2k and G2(p,2k) contains only 0 as a fixed point where k≥4 and p≡5(mod8).
Proof. For k≥4,α=1+2k−2 is fixed point if αp≡α(mod2k). For this, note that
(1+2k−2)p=1+p2k−2+p∑β=2(pβ)2β(k−2). | (1.4) |
As k≥4, Lemma 1.5 invokes, k≥4,k≤β(k−2),β=2,3,4,…,n. Then 2k|2β(k−2). Hence
p∑β=2(pβ)2β(k−2)≡0(mod2k). | (1.5) |
Also, p=8t+5 for some integer t=0,1,2,…. Using p together with Eq (1.5) in (1.4), we get
(1+2k−2)p≡1+(5+8t)2k−2(mod2k)≡1+(1+22+23t)2k−2(mod2k)≡1+(2k+2k−2+2k+1t)(mod2k)≡1+2k−2(mod2k). |
The remaining fixed points can be proved in a similarly technique. Also by Theorem 1.4, the number of solutions of up−1≡1(mod2b)with2∤u is (gcd(2,p−1))η1⋅(gcd(2b−2,p−1))η2. In our case, take η1=η2=1,withb≥4. As p≡5(mod8) implies that p−1=4(1+2t),t∈Z+. Hence, we get gcd(2,4(1+2t))⋅gcd(2b−2,4(1+2t))=2⋅4=8. This shows that there are exactly eight fixed points.
Figure 2 reflects Proposition 1.7.
The vertices v1,v2,v3,…,vt compose a component if for every j,1≤j≤t, there exists some i,1≤i≤t, such that vpj≡vpi(modm), for all j≠i. By [8], it has been established that there exists one and only one cycle in every component of such digraphs. While the enumeration of components is still an open problem. In this section, an enumeration of cycles and components (up to isomorphism) of G(p,2k) is proposed for certain classes of p. Also, we examine all integers for which there are p number of components. The following theorem also validates a similar result given in [4] for a quadratic congruences.
Theorem 2.1. For an odd prime p, define m=2ipt,i=0,1,2,t≥1. Then G(p,m) contains an s-cycle if and only if ps≡1(modd) for a smallest integer s>0 provided d>0 with d∣λ(m).
Proof. Let m=2ipt,i=0,1,2,t≥1 and suppose G(p,m) contains an s-cycle. Assume that u is an arbitrary vertex on this cycle. Then ups≡u(mod2ipt) for a smallest integer s>0. That is, u(ups−1−1)≡0(mod2ipt). Clearly, gcd(u,ups−1−1)=1. Thus if we let m1=gcd(u,m) and m2=m/m1, then s>0 must be smallest such that u≡0(modm1) and vps−1≡1(modm2). Using Chinese Reminder Theorem, we get a solution x to satisfying x≡1(modm1) and x≡a(modm2). Consequently, the integer s>0 is, in fact, least such that xps−1≡1(modm1) and xps−1≡1(modm2). Both yields that, xps−1≡1(mod2ipt). Let d=ordxm(d=ordxm if d is the least positive integer such that xd≡1(modm)). Then, x≡1(modm1) enforces that s>0 is the least integer such that ps≡1(modd). Also, if d=ordxm, then (x,2ipt)=1, so by Carmichael Theorem, it is evident that d|λ(2ipt).
Conversely, suppose d>0 with d|λ(m) and let u=gλ(2ipt)|d. Then d=ordum. As d|ps−1 but d∤pl−1 for 0≤l<s. We deduce that the integer s>0 is least so that ups−1≡1(mod2ipt). Equivalently, u⋅ups−1≡ups≡u(mod2ipt).
Theorem 2.2. For any prime p with p≡3(mod8), the vertices 1+ps2k−2,k≥4 for s=0,1 form a cycle of length 2 in G(p,2k).
Proof. The vertices α0 and α1 form a cycle of length 2 in G(p,2k) if and only if αp0≡α1(mod2k),αp1≡α0(mod2k). Now
(1+ps2k−2)p=1+ps+12k−2+p∑β=2(pβ)pβs2β(k−2). | (2.1) |
As k≥4, Lemma 1.5 invokes, k≥4,k≤β(k−2),β=2,3,4,…,n. That is, 2k|2β(k−2). Therefore,
p∑β=2(pβ)pβs2β(k−2)≡0(mod2k). | (2.2) |
(1+ps2k−2)p≡1+ps+12k−2(mod2k), | (2.3) |
s=0,1 and p≡3(mod8). Also, p=8t+3 for some integer t=0,1,2,…. Using this together with Eq (2.3), for s=1 we get that
(1+ps2k−2)p≡1+(3+23t)22k−2(mod2k)≡1+(9+26t2+3.24t)2k−2(mod2k)≡1+(1+23+26t2+3.24t)2k−2(mod2k)≡1+(1+23+26t2+3.24t)2k−2(mod2k)≡1+2k−2(mod2k). | (2.4) |
From Eqs (2.3) and (2.4), we find that the vertices 1+ps2k−2 for s=0,1 form a cycle of length 2 in G(p,2k), where k≥4 and p≡3(mod8).
Theorem 2.3. For any prime p such that p≡3(mod8), the vertices 2k+pps,k>2 for s=0,1,2,3,…,2k−2−1 form a cycle of length 2k−2 in G(p,2k).
Proof. The vertices α0,α1,α2,…,α2(k−2)−1 form a cycle of length 2k−2 in G(p,2k) if and only if αp0≡α1(mod2k),αp1≡α2(mod2k),…,αp2(k−2)−1≡α0(mod2k). Now
(2k+pps)p=2k+(pps)p+p∑β=2(pβ)(pps)p−β2(β(k)), | (2.5) |
Since k>2,k≤β(k),β=1,2,3,4,…,n. Then 2k|2β(k). Hence,
p∑β=2(pβ)(pps)p−β2β(k)≡0(mod2k), | (2.6) |
putting in Eq (2.5), we get
(2k+pps)p≡2k+pps+1(mod2k), | (2.7) |
s=0,1,2,3,…,2(k−2)−1 and p≡3(mod8). Finally, we noted that
(2k+pp2(k−2)−1)≡2k+p(mod2k). | (2.8) |
Since, p2(k−2)−1≡1(mod2k), for any k>2 it implies that,
pp2(k−2)−1≡p(mod2k). |
Eqs (2.7) and (2.8) give that vertices 2k+pps,k>2 for s=0,1,2,3,…,2(k−2)−1 form a cycle of length 2k−2 in the graph G(p,2k), where p≡3(mod8).
Theorem 2.4. For any prime p such that p≡3(mod8), the vertices 2k+(p+2)ps,k>2 for s=0,1,2,3,…,2k−2−1 form a cycle of length 2k−2 in the graph G(p,2k).
The proof is on similar lines as illustrated in the proof of Theorem 2.3.
The following result is a simple consequence of last two theorems.
Corollary 2.5. For any prime p such that p≡3(mod8), the graph G(p,2k) has cycle of length 2k−(r+2), where k>2,0≤r≤k−3.
In the following theorem, we find all integers for which there are p components.
Theorem 2.6. (1) The number of components of G(p,m) is p if m=pk for some positive integer k and p is an odd prime.
(2)The number of components of G(p,m) is p if m is prime of the form m=(p−1)×pk+1 for some positive integer k, where p≡3(mod4).
Proof. (1) If m=pk then by [[8], Theorem 6.6 on page 2005], we have exactly p fixed points. Now these are either isolated or the roots of their respective components. Thus, if m is any number for which we have more than p components then there must be a cycle of length s>1. But then by Theorem 2.1, s is the least positive integer such that ps≡1(modd), where d∣λ(pk) and d>0. That is, d∣ps−1 and d∣λ(m)=(p−1)×pk as well. This clearly enforces that d=p−1. But then pk≡1(modp−1) for each value of k. In particular, if 1≤r<s, then pr≡1(modp−1) as well. This has certainly provided a contradiction against the minimality of s. Thus, this case is not all possible. Consequently, G(p,m) has p components.
(2) If m is prime of the form m=(p−1)×pk+1 for some positive integer k, where p≡3(mod4). Then it can easily be seen that there are p fixed points by [[8], see Theorem 6.6 on page 2005] and by similar argument as part 1 there does not exist cycle of length greater than 1. Thus, there are exactly p components.
If d is the least positive integer such that nd≡1(modm) then d will be termed as order of n modulo m, it is denoted as d=ordnm. In the following result, we show that the digraph G1(p,2k),k>0 contains only the cycles of lengths which are the powers of 2 (excluding fixed points) and G2(p,2k) form a tree with root 0.
Theorem 2.7. For any positive integer k, the digraph G1(p,2k), contains cycles of lengths as integral powers of 2. That is, the length of any cycle in G1(p,2k) must be of the form 2t,t∈Z+ and t<k (excluding fixed points) while G2(p,2k) form a tree with root 0. Moreover, indeg(0)=2k−⌈kp⌉.
Proof. It is well known that there must be an equal number of residues of m=2k which are prime to m and those which are not prime to m. Thus the digraphs G1(p,m) and G2(p,m) contains equal number of vertices 2k−1, by Lemma 1.6. It can be seen that, ±1+2k−1,−1+2k,1, are the only fixed points of G1(p,2kp), where p≡3(mod4), and by Proposition 1.7. G1(p,2k) has 8 fixed points which are 1,2k−1±1,±1+2k−2,2k−1,−(2k−2±1)+2k, where p≡5(mod8), and if p=2ua+1 (p≡1mod8) with an odd a, then G1(p,2k) contains 2u+1 fixed points, the elements of order dividing 2u, provided that k≥u+2. By Theorem 2.1, there would be a cycle of length s if and only if s=ordpd, for some divisor d of λ(m)=2k−2. Now if there exists such a cycle, then s being order of p modulo a divisor of 2k−1 must be of the form 2t, for some integer t>0. As far the other case is concerned, we note that all, even residues of 2k, will be connected by a tree. Thus, (2k−⌈kp⌉) numbers, namely 2⌈kp⌉,2⋅2⌈kp⌉,3⋅2⌈kp⌉,…,2k−⌈kp⌉⋅2⌈kp⌉ are mapped onto 0. Consequently, indeg(0)=(2k−⌈kp⌉).
In the following theorem, we investigate the structure of isomorphic trees.
Theorem 2.8. Let t be any positive integer and m=pt. Then the digraph G1(p,m) consists of p−1 isomorphic trees. Moreover, G2(p,m) is a tree with root at 0 and indeg(0)=pt−⌈tp⌉.
Proof. We know that the digraph G(p,m) has exactly p components with p fixed points (For detail, see Theorem 6.6 on page 205 in [8]). Note that pt−⌈tp⌉ elements, namely, p⌈tp⌉,2⋅pt−⌈tp⌉,3⋅pt−⌈tp⌉,…,pt−⌈tp⌉⋅p⌈tp⌉ are adjacent to 0 in G2(p,m). Also, p|ϕ(m)=(p−1)⋅pt−1, by Theorem 3.3, we obtain that the digraph G1(p,m) is semiregular and every vertex, either has degree 0orp. It is clear that this digraph has a tree with root 0. Now assume the set of non-zero fixed points as {1,a2,a3,…,ap−12,m−1,m−a2,m−a3,…,m−ap−12}. Define T1,Tm−1,Ta2,Tm−a2 so on Tap−12 and Tm−ap−12 trees containing the fixed points {1,m−1,a2,m−a2,a3,m−a3,…,ap−12,m−ap−12}, respectively. we can easily deduce that T1≅Tm−1, Ta2≅Tm−a2,…,Tap−12≅Tm−ap−12. Now, if we multiply each vertex of the tree T1 by number a2, we have tree Ta2. Similarly, if we multiply each vertex of the tree T1 by number a3, we have a tree Ta3. By continuing this fashion if we multiply T1 by ap−12 have a tree Tap−12. This is possible if gcd(ai,m)=1, where i=1,2,3,…,ap−12. Consequently, it yields that, T1≅Ta2,T1≅Ta3,…,T1≅Tap−12.
Figures 3 and 4 reflect Theorem 2.7 and Theorem 2.8, respectively.
Now, we discuss the components of the digraph G(p,m). The notation At(G(p,m)) denotes the number of cycles of length t in the digraph G(p,m).
Theorem 2.9. For any prime p such that p≡3(mod8), the graph G(p,2k) has 11+4(k−5) components, where k>4.
Proof. To prove this result, first we find the number of cycles of length 2k−(r+4), where k>4,0≤r≤k−5 and p≡3(mod8). By Lemma 1.5, it is found that A1(G(p,2k))=5 and obtained the number of cycles of length two A2(G(p,2k)) by using Theorem 6.6 of [8] for δi=2, given as
A2(G(p,2k))=12[(2gcd(λ(2k),p2−1)+1)−∑d|2d≠2dAd(2k,p)]. |
Now gcd(λ(2k),p2−1)=8, where p≡3(mod8),k>4 and A1(p,2k)=5, hence, A2(G(2k,p))=6
A22(G(p,2k))=122[(2gcd(λ(2k),p22−1)+1)−∑d|22d≠22dAd(p,2k)], |
gcd(λ(2k),p22−1)=24=16,p≡3(mod8),k>4, A1(p,2k)=5 and A2(p,2k)=6.
A22(G(p,2k))=4.A23(G(p,2k)=123[(2gcd(λ(2k),p23−1)+1)−∑d|23d≠23dAd(p,2k)]. |
gcd(λ(2k),p23−1)=25=32,p≡3(mod8),k>4, A1(p,2k)=5, A2(p,2k)=6, and A3(p,2k)=4.
A23(G(p,2k))=4. |
⋮ |
A2k−4(G(p,2k))=12k−4[(2gcd(λ(2k),p2k−4−1)+1)−∑d|2k−4d≠2k−4dAd(p,2k−4)], |
gcd(λ(2k),p2k−4−1)=2k−2,p≡3(mod8),k>4, A1(p,2k)=5, A2(p,2k)=6,A22(p,2k)=A23(p,2k)=…=A2k−4(p,2k)=4.
A2k−4(G(p,2k))=4. |
So by counting principle adding A1(p,2k)=5, A2(p,2k)=6,A22(p,2k)=A23(p,2k),…,A2k−4(2k,p)=4. We get 11+4(k−5) components, for k>4, and p≡3(mod8).
Theorem 2.10. For any prime p such that p≡5(mod8), the graph G(p,2k) has 13+4(k−5) components, where k>4.
The proof is on similar lines as illustrated in the proof of Theorem 2.9.
Theorem 2.11. Let p be any prime such that p≡7(mod24). Then graph G(p,2k) has 19+8(k−6) components, where k>5.
The proof is on similar lines as illustrated in the proof of Theorem 2.9.
Figure 5(a) and (b) reflect Theorem 2.9.
In this section, we give conditions for the regularity and semiregularity of our proposed graph. In the following result, we characterize the regularity of the digraph G1(p,m).
Lemma 3.1. The digraph G1(p,m) is regular if and only if p∤ϕ(m), where ϕ is the Euler's function.
Proof. We suppose that G1(p,m) is regular. The regularity of G1(p,m) yields that the indeg(v)=1 for every vertex v in G1(p,m). This means that xp≡v(modm) has a unique solution. Without loss of generality, assume v≡1(modm) and let β be the unique solution of the congruence xp≡1(modm). That is, βp≡1(modm). Now, if p∣ϕ(m) then ϕ(m)=p⋅t for some integer t. Note that, t=1 is impossible as ϕ(m) is always even. Also by Euler Theorem, βϕ(m)≡1(modm) as (β,m)=1 (by definition of G1(m)). Then, βp⋅t≡1(modm) or (βt)p≡1(modm). This shows that βt,t>1 is another solution of xp≡1(modm). This means that indeg(1)=2, a contradiction against the fact that G1(p,m) was regular. Therefore, p∤ϕ(m). Conversely, let p∤ϕ(m) and we suppose that G1(p,m) is not regular. Then there must be at least one vertex α such that indeg(α)>1. For the sake of convenience, take α=1 with indeg(α)=2. This means that xp≡1(modm) has two solutions. Let these be α and αt,t>1. Then, αp≡1(modm) and αp′t≡1(modm). But, αϕ(m)≡1(modm). Hence, we deduce that either ϕ(m)=p or ϕ(m)=p⋅t. As ϕ(m) is always even, so ϕ(m)=p⋅t. That is, p∣ϕ(m), a contradiction.
Lemma 3.2. Let m>0 be any square free integer and p be any odd prime. The digraph G(p,m) is cyclic if and only if p∤ϕ(m).
Proof. Recall that a digraph is cyclic if all of its components are cycles. Also, every regular digraph is cyclic. Hence, by Lemma 3.1, G1(p,m) is cyclic if and only if p∤ϕ(m). For G2(p,m), suppose p∤ϕ(m) and let α be any vertex in G2(p,m). Let p′ be an odd prime such that p′∣gcd(α,m). Then we can find integers r and s such that α=rp′ and m=p′s with gcd(r,s)=1. Now if β is the solution of the congruence xp≡α(modm), then βp≡α(modm) yields that βp=α+mt for some integer t. But then βp=rp′+sp′t. Consequently, p′∣β such that p′∣gcd(α,m). This means that βp≡α≡0(modp′). Thus we conclude that a number β exists such that it is a solution of xp≡α(modm). Next we show that this solution is unique modulo m. Since p∤ϕ(m), so gcd(p,ϕ(p′))=1. Then the linear congruence py≡1(modp′−1) has a unique solution in y. Finally, we put β≡αy(modp′) to get βp≡αp.y≡a(modp′). By Chinese Reminder Theorem, we get that β is a unique solution of xp≡α(modm). Thus, indegree of this arbitrary vertex is one. This certainly implies that every vertex is either a loop (a cycle of length one) or at some cycle. The converse is a direct consequence of Lemma 3.1.
For further result on semiregularity, we define a function η as,
η(m)={ηo(m)+1ifp2|mηo(m)ifp2∤m, |
where ηo(m) is the number distinct prime divisors of m such that p′≡1(modp). In the following theorem, we characterize the semiregularity of G1(p,m), where p is an odd prime.
Theorem 3.3. The digraph G1(p,m) is semiregular if and only if p|ϕ(m), Also the indegrees in G1(p,m) are either pη(p) or zero.
Proof. By definition of digraph G1(p,m), it is indicated, that βϕ(m)≡1(modm) for each vertex β in G1(p,m). This means that the indegrees of the vertices of G1(p,m) are same if indeg(β)>0. To find the indeg(β)>0, we just count the indegrees of 1. For this purpose we just count the number of solutions of the congruence, xp≡1(modpr). Let p be an odd prime and r be any positive integer. Then we see that, (pr−1+1)p≡1(modpr). Likewise, we see that the numbers, 2×pr−1+1,3×pr−1+1,4×pr−1+1,5×pr−1+1,6×pr−1+1,…,p×pr−1+1 also solutions of the congruence, xp≡1(modpr). While modulo p′, there are always p′ solutions whenever p′≡1(modp) and there is a trivial solution if p′≢1(modp) (for detail see [26], page 104). Using the canonical representation of m into odd primes and Chinese Remainder Theorem, simultaneously, we must get that αp≡1(modm) either have pη(m) solutions or have no solution for each vertex α in G1(p,m). On the other hand, we let G1(p,m) is semiregular and indeg(α)=pη(m) for α∈G1(p,m). This means that αp≡1(modm). Using multiplicative order and Euler Theorem for α, we deduce that p∣ϕ(m). Conversely, assume that p∤ϕ(m). then by Lemma 3.2 indegree of each vertex is one which is contradiction. Hence p∣ϕ(m).
Figure 6 reflects Theorem 3.3.
Until the date, several papers on power diagraphs have been published for the fixed power of the congruences modulo an integer. For example, power diagraphs corresponding to x2=y(modm), x3=y(modm) or else fixed powers have been discussed earlier. In this work, we discussed and generalized the results of power diagraphs for any odd prime p as x power rather fixing. That is, for the congruence of xp=y(modm), where p is any odd prime. We addressed the number of loops, cyclic structures, tree structures and the enumeration of components over residue classes of integers. In Section 1, the fixed points of such diagraphs are described and enumerated. These fixed points are referred to as loops. The existence and enumeration of cycles along with their sizes are discussed in Theorems 2.1–2.4 and in Corollary 2.5. In Theorems 2.6–2.11, we have discussed the enumeration of components and trees for classes of integers. These findings have also been shown in Figures 2–5 for better comprehension and confirmation. Finally, the results on regularity and semi-regularity are discussed and generalized in Section 3. In fact, we have fully established and defined the desired ideas for power diagraphs with an odd prime power. We believe that the characterizations can be built on the basis of these findings for all composite modules, which can serve as a basis for solving many difficult and open challenges.
This work was funded by the Deanship of Scientific Research (DSR) at King Abdulaziz University, Jeddah. The authors, therefore, acknowledge with thanks DSR for technical and financial support.
The authors declare that they have no conflict of interest regarding the publication of the research article.
[1] | S. Bryant, Groups, graphs, and Fermat's last theorem, Am. Math. Monthly, 74 (1967), 152–155. |
[2] | L. Szalay, A discrete iteration in number theory, BDTF Tud. Közl., 8 (1992), 71–91. |
[3] |
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
![]() |
[4] | L. Somer, M. Krizek, On a connection of number theory with graph theory, Czech. Math. J., 5 (2004), 465–485. |
[5] | M. K. Mahmood, F. Ahmad, An informal enumeration of squares of 2k using rooted trees arising from congruences, Utilitas Math., 105 (2017), 41–51. |
[6] | M. A Malik, M. K Mahmood, On simple graphs arising from exponential congruences, J. Appl. Math., 2012 (2012), 1–10. |
[7] |
Y. J. Wei, G. Tang, The iteration digraphs of finite commutative rings, Turk. J. Math., 39 (2015), 872–883. doi: 10.3906/mat-1503-2
![]() |
[8] |
L. Somer, M. Krizek, On symmetric digraphs of the congruence xk≡y(modm), Discrete Math., 309 (2009), 1999–2009. doi: 10.1016/j.disc.2008.04.009
![]() |
[9] | J. Skowronek-Kazió, Some digraphs arising from number theory and remarks on the zero-divisor graph of the ring Zn, Inf. Process. Lett., 108 (2008), 165–169. |
[10] | M. H. Mateen, M. K. Mahmood, A new approch for the enumeration of components of digraphs over the quadratic maps, J. Prime Res. Math., 16 (2020), 56–66. |
[11] |
M. K. Mahmood, F. Ahmad, A classification of cyclic nodes and enumerations of components of a class of discrete graphs, Appl. Math. Inf. Sci., 9 (2015), 103–112. doi: 10.12785/amis/090115
![]() |
[12] | M. H. Mateen, M. K. Mahmood, Power digraphs associated with the congruence xn≡y(modm), Punjab Univ. J. Math., 51 (2019), 93–102. |
[13] | M. H. Mateen, M. K. Mahmood, S. Ali, Importance of power digraph in computer science, International conference on innovative computing (ICIC), Lahore, Pakistan, (2019), 1–6. |
[14] |
S. Akbari, A. Mohammadian, On the zero-divisor graph of a commutative ring, J. Algebra, 274 (2004), 847–855. doi: 10.1016/S0021-8693(03)00435-6
![]() |
[15] | Y. J. Wei, J. Z. Nan, G. H. Tang, H. D. Su, The cubic mapping graphs of the residue classes of integers, Ars Combin., 97 (2010), 101–110. |
[16] |
Y. Wei, G. Tang, H. Su, The square mapping graphs of finite commutative rings, Algebra Colloq., 19 (2012), 569–580. doi: 10.1142/S1005386712000442
![]() |
[17] | M. Rezaei, S. U. Rehman, Z. U. Khan, A. Q. Baig, M. R. Farahani, Quadratic residues graph, Int. J. Pure Appl. Math., 113 (2017), 465–470. |
[18] | W. Carlip, M. Mincheva, Symmetry of iteration graphs, Czechoslovak Math. J., 58 (2008), 131–145. |
[19] |
G. Deng, P. Yuan, On the symmetric digraphs from powers modulo n, Discrete Math., 312 (2012), 720–728. doi: 10.1016/j.disc.2011.11.007
![]() |
[20] |
Y. Meemark, N. Wiroonsri, The quadratic digraph on polynomial rings over finite fields, Finite Fields Appl., 16 (2010), 334–346. doi: 10.1016/j.ffa.2010.05.004
![]() |
[21] |
Y. Meemark, N. Wiroonsri, The digraph of the kth power mapping of the quotient ring of polynomials over finite fields, Finite Fields Appl., 18 (2012), 179–191. doi: 10.1016/j.ffa.2011.07.008
![]() |
[22] | M. K. Mahmood, S. Ali, A novel labeling algorithm on several classes of graphs, Punjab Univ. J. Math., 49 (2017), 23–35. |
[23] | S. Ali, M. K. Mahmood, New numbers on euler totient function with application, J. Math. Ext., 14 (2019), 61–83. |
[24] |
H. Alolaiyan, A. Yousaf, M. Ameer, A. Razaq, Non-conjugate graphs associated with finite groups, IEEE Access, 7 (2019), 122849–122853. doi: 10.1109/ACCESS.2019.2938083
![]() |
[25] |
A. Portilla, J. M. Rodrguez, J. M. Sigarreta, E. Tours, Gromov hyperbolicity in directed graphs, Symmetry, 12 (2020), 105–117. doi: 10.3390/sym12010105
![]() |
[26] | I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Hoboken: John Wiley & Sons Inc., 1991. |
[27] |
R. D. Carmichael, Note on a new number theory function, Bull. Am. Math. Soc., 16 (1910), 232–238. doi: 10.1090/S0002-9904-1910-01892-9
![]() |
[28] | B. Wilson, Power digraphs modulo n, Fibonacci Quart., 36 (1996), 229–239. |
[29] | M. K. Mahmood, S. Ali, On super totient numbers with applications and algorithms to graph labeling, Ars Combinatoria, 143 (2019), 29–37. |
1. | Shi Yin, Fengyu Guo, Yuanyuan Yu, Yibo Li, Kifayat Ullah, Practical teaching method innovation decisions related to labor and reading at agricultural colleges based on entropy-fuzzy AHP combination weights, 2023, 8, 2473-6988, 7641, 10.3934/math.2023383 | |
2. | Carlos Andres Martos Ojeda, Luis Miguel Delgado Ordonez, Carlos Alberto Trujillo Solarte, Bh Sets as a Generalization of Golomb Rulers, 2021, 9, 2169-3536, 118042, 10.1109/ACCESS.2021.3106617 | |
3. | Sabir Hussain, Farkhanda Afzal, Deeba Afzal, Dhana Kumari Thapa, Haidar Ali, The Study about Relationship of Direct Form of Topological Indices via M-Polynomial and Computational Analysis of Dexamethasone, 2022, 2022, 2090-9071, 1, 10.1155/2022/4912143 | |
4. | M. Haris Mateen, M. Khalid Mahmood, Shahbaz Ali, M. D. Ashraful Alam, Haidar Ali, On Symmetry of Complete Graphs over Quadratic and Cubic Residues, 2021, 2021, 2090-9071, 1, 10.1155/2021/4473637 | |
5. | M. Haris Mateen, M. Khalid Mahmood, Daud Ahmad, Shahbaz Ali, Shajib Ali, Haidar Ali, A Paradigmatic Approach to Find Equal Sum Partitions of Zero-Divisors via Complete Graphs, 2022, 2022, 2090-9071, 1, 10.1155/2022/1587689 | |
6. | M. Haris Mateen, Muhammad Khalid Mahmmod, Doha A. Kattan, Shahbaz Ali, A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs, 2021, 6, 2473-6988, 9998, 10.3934/math.2021581 | |
7. | Sufyan Asif, Muhammad Khalid Mahmood, Amal S. Alali, Abdullah A. Zaagan, Structures and applications of graphs arising from congruences over moduli, 2024, 9, 2473-6988, 21786, 10.3934/math.20241059 | |
8. | Hamza Daoub, Osama Shafah, Ahmad Almutlg, Exploring a Graph Complement in Quadratic Congruence, 2024, 16, 2073-8994, 213, 10.3390/sym16020213 |