# On Symmetry of Complete Graphs over Quadratic and Cubic Residues

Authors: M. Haris Mateen; M. Khalid Mahmood; Shahbaz Ali; M. D. Ashraful Alam
Journal: Journal of Chemistry
 (2021)

---

## Abstract

In this study, we investigate two graphs, one of which has units of a ringZn as vertices (or nodes) and an edge will be built between two vertices u and v if and only if u3≡v3modn. This graph will be termed as cubic residue graph. While the other is called Gaussian quadratic residue graph whose vertices are the elements of a Gaussian ring Zni of the form α=a+ib,β=c+id, where a,b,c,d are the units of Zn. Two vertices α and β are adjacent to each other if and only if α2≡β2modn. In this piece of work, we characterize cubic and Gaussian quadratic residue graphs for each positive integer n in terms of complete graphs.


---

## Body

## 1. Introduction

Graph theory plays a dynamic role in computer science, biological sciences, chemistry, and physics [1–7]. Graphs can also be found in other frameworks related to social and information systems [1]. Graphs are used to solves many issues related to everyday life. Many circuits are constructed in physics with the use of graphs [4]. Many unknown atomic numbers of molecules are found in a few years ago, using group symmetry through graphs [5]. In computer science, many problems are discussed by means of graphs which were not easy to visualize earlier. For discrete mathematics and combinatorics, the application of number theory and graph theory is of crucial importance. In this work, we employ this drive to investigate two special classes of graphs.The concept of square mappingx2⟶y under modulo prime number is discussed by Rogers in [8]. The structure of digraphs under quadratic mapping modulo composite integers is discussed by Somer and Krizek in [9]. Mahmood and Ahmad proposed many new results of graphs over residues modulo prime powers in [10, 11]. Mateen and Mahmood investigated the structure of power digraphs associated with the congruence xn≡ymodm and xn≡ynmodm in [12–15]. In [16], Wei and Tang introduced the concept of square mapping graphs of the Gaussian ring Zni. In this study, we fully characterize cubic and Gaussian quadratic residue graphs for each positive integer n in terms of complete graphs. Before introducing results for cubic and Gaussian quadratic residues graphs, we give some earlier results without proofs for use in the sequel.Theorem 1 (See [17]).
Ifp is a prime number of the form p≡1mod3, then the number of different cubic residues in modp is p+2/3.Theorem 2 (See [17]).
Ifp is a prime of the form p≡2mod3, then there are exact p cubic residues in modp different from each other. In other words, all elements of Zp are cubic residues.Theorem 3 (See [18]).
Letp be a prime number and k is any arbitrary positive integer. Suppose that u is a solution of fx≡0modpk.(1)
Ifp∤f′u, then there is only one solution uk+1 of fx≡0modpk+1, such that uk+1≡umodpk. The solution uk+1 is given by uk+1=u+pkv, where v is the unique solution of f′ut≡−fu/pkmodp.(2)
Ifp|f′u and pk+1|fu, then there are p solutions of fx≡0modpk+1 that are congruent to u modulo p, given by u+pkv for v=0,1,2,…,p−1.(3)
Ifp|f′u and pk+1∤fu, then there are no solutions of fx≡0modpk+1 that are congruent to u modulo pkTheorem 4 (See [19]).
Leta be odd. Then, we have the following:(1)
The equationx2≡amod2 has the unique solution x≡1mod2(2)
The equationx2≡amod4 either has no solution if a≡3mod4 or has two solutions x≡1,3mod4 if a≡1mod4(3)
Whenk≥3, the equation x2≡amod2k either has no solution if a≢1mod8 or has four solutions x1,−x1,x1+2k−1,−x1+2k−1 if a≡1mod8Definition 1 (See [20]).
Letp be an odd prime and a any integer. The Legendre symbol a/p is defined as(1)ap=1,ifais quadratic residuemodp,0,p|a,−1,ifais quadratic nonresiduemodp.


## 2. Cubic Residues Graphs

In this section, we elaborate the concept of cubic residue graph and then characterize these graphs completely for each positive integern. The disjoint union of the graphs H and K is expressed by H⊕K, and the disjoint union of the n copies of the graph K is denoted as nK=K⊕K⊕⋯⊕K.Definition 2.
Letn be a positive integer. A simple graph G^3,n is said to be cubic residue graph if the vertex set of the graph G^3,n is VG^3,n=v∈Z+|v,n=1andv<n and the edge set of G^3,n is EG^3,n=uv|u,v∈VG^3,nandu3≡v3modn.Example 1.
Forn=27, the vertex set of G^3,27 is 1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26. We can easily see that 13≡103≡193≡1mod27, 23≡113≡203≡8mod27, 43≡133≡223≡10mod27, 53≡143≡233≡17mod27, 73≡163≡253≡19mod27, and 83≡173≡263≡26mod27. G^3,27=6K3 is shown in Figure 1.Figure 1
G^3,27=6K3.In the following result, we characterize cubic residues graphs for the class of integers of the form2k and pk, where p is an odd prime.Theorem 5.
LetG^3,n be a cubic residue graph. Then,(a)
The graphG^3,n,k≥1 is empty(b)
Ifp≡5mod6, then the graph G^3,pk,k≥1 is empty(c)
Ifp≡1mod6, then G^3,pk=pk−1p−1/3K3,k≥1(d)
The graphG^3,3k=2⋅3k−2K3,k≥2Proof.
(a)
Letn=2k,k≥1 be an integer. The distinct vertices a and b are adjacent only when congruence a3≡b3mod2k has a solution, where a,b∈Z2k with a,2k=1=b,2k. The congruence a3≡b3mod2k implies a3−b3=a−ba2+ab+b2≡0mod2k. Thus, a≡bmod2k or a2+ab+b2≡0mod2k. Both congruence show that there does not exists any integer a and b from Z2k, with a,2k=1=b,2k, such that the congruence a3≡b3mod2k has a solution. Thus, G^3,2k,k≥1 is empty graph.(b)
Since,p=5mod6 implies p=2mod3. Thus, by Theorem 1, all cubic residues of modpk,k≥1 are different; therefore, graph G^3,pk,k≥1 with p≡1mod6 is empty.(c)
By Theorem2, the number of nonzero different cubic residues of modpk is pk−1p−1/3. Thus, G^3,pk=pk−1p−1/3K3,k≥1.(d)
An integera is a cubic residue of mod3k if and only if the congruence x3≡amod3k is solvable, and in this case, the cubic residues are different only if x belongs to the set S=1,2,4,5,7,…,3k−1−2,3k−1−1. The cardinality of the set S is 2⋅3k−2. The proof is done if we show exactly two more residues that are relatively prime to 3k other than from the element of S.(2)13≡1=13mod3k1=1+33k−3+3k1+3k−1=1+3k−13mod3k1=1+23⋅33k−3+2⋅3k1+2⋅3k−1=1+2⋅3k−13mod3k23≡8=23mod3k8=23+33k−3+2⋅3k1+3k−1=2+3k−13mod3k8=23+23⋅33k−3+4⋅3k2+2⋅3k−1=2+2⋅3k−13mod3k43≡64=43mod3k64=1+31+3k−23=1+331+3k−23+321+3k−21+31+3k−2mod3k64=1+31+2⋅3k−23=1+331+2⋅3k−23+321+2⋅3k−21+31+2⋅3k−2mod3k⋮3k−1−23≡−8mod3k−8=2⋅3k−1−23=−8+23⋅33k−3−3⋅4⋅3k−12⋅3k−1−2mod3k−8=3⋅3k−1−23=−8+33k−2⋅3k+13⋅3k−1−2mod3k3k−1−13≡−1mod3k,−1=2⋅3k−1−13=−1+33k−3−3⋅2⋅3k−12⋅3k−1−1mod3k,−1=3⋅3k−1−13=−1+33k−3k+13⋅3k−1−1mod3k.
Hence, the reduced residue system ofZ3k,k≥2 has exactly 2⋅3k−2 nonzero cubic residues. Thus, graph G^3,3k is 2⋅3k−2K3.In the following theorem, we find those integers for which cubic residues graphs are empty. This means that there is no connection between any two vertices of cubic residue graph.Theorem 6.
Ifm=3⋅2α⋅∏i=1rpiβi, α and βi≥1 with each pi≡5mod6, then G^3,m is empty.Proof.
Letm=3⋅2α⋅∏i=1rpiβi be an integer, with α and βi≥1 and pi≡5mod6. By Theorem 2, all cubic residues of Z3, Z2α, and Z∏i=1rpiβi are different. Since 3, 2α, and ∏i=1rpiβi are relatively prime to each other, so no residues of Zm are connected to each other. Thus, graph G^3,m is empty.Theorem 7.
Ifm=∏i=1rpiβi and βi≥1 with each pi≡1mod6, then G^3,m=φm/3rK3r.Proof.
Letm=∏i=1rpiβi, and βi≥1 be an integer with each pi≡1mod6. Since each pi≡1mod6, so by Theorem 1, the number of nonzero distinct cubic residues in modp is p−1/3 and thus in modm is φm/3r. Therefore, by Chinese reminder theorem (CRT), the reduced residue system of Zm has 3r number of distinct solutions. Hence, G^3,m=φm/3rK3r.The coming result is the main result of this section that characterizes cubic residue graph for each positive integern.Theorem 8.
Ifm=2α⋅3β⋅∏i=1rpiαi⋅∏j=1sqjβj, αi,βj≥1, with each pi≡1mod6 and qj≡5mod6, then(3)G^3,m=φm3rK3r,ifα≥0,β=0or1,φm3r+1K3r+1,ifα≥0,β≥2.Proof.
Letm=2α⋅3β⋅∏i=1rpiαi⋅∏j=1sqjβj, αi,βj≥1 with each pi≡1mod6, and qj≡5mod6. When α≥0,β=0 or 1, then proof is done by Theorem 5, and when α≥0,β≥2, by using CRT and Theorem 5 part (c) and (d), we have Theorem 8.The cubic residues graph forn=91 is shown in Figure 2.Figure 2
G^3,91=8K9.


## 3. Gaussian Quadratic Residues Graphs

In this section, we give the concept of a Gaussian quadratic residue graph and then characterize these graphs.Definition 3.
A simple graphG˜2,n is called quadratic residue graph if the vertex set VG˜2,n=v=a+ib|a,b∈Zn,a,n=1=b,n and EG˜2,n=e=a+ib⟷c+id⟺a+ib2≡c+id2modn|a+ib,c+id∈VG˜2,n.The Gaussian quadratic residues graph forn=5 is shown in Figure 3.Figure 3
G˜2,5=4K2⊗2K4.The following theorem characterizes Gaussian quadratic residues graphsG˜2,n for the class of integers of the form n=2t, where t is a positive integer.Theorem 9.
Letn be an integer; then,(4)G˜2,n=K1,ifn=2,K4,ifn=22,2⋅K8,ifn=23,22t−6⋅K16,ifn=2t,t≥4.Proof.
Letn=2 be an integer; then, the vertex set has only one element, namely, 1+i, so G˜2,n is empty. If n=24, then the vertex set of G˜2,22 is 1+i,3+i,1+3i,3+3i, clearly 1+i2≡1+3i2≡3+i2≡3+3i2≡2imod4. Thus, each vertex of G˜2,22 are connected to each other; hence, we have K4. For n=23, the vertex set of G˜2,23 is 1+i,3+i,5+i,7+i,1+3i,3+3i,5+3i,7+3i,1+5i,3+5i,5+5i,7+5i,1+7i,3+7i,5+7i,7+7i. Since,(5)2i≡1+i2,mod8,1+5i2,mod8,5+i2,mod8,3+3i2,mod8,3+7i2,mod8,7+3i2,mod8,5+5i2,mod8,7+7i2,mod8,,6i≡1+3i2,mod8,3+i2,mod8,1+7i2,mod8,7+i2,mod8,3+5i2,mod8,5+3i2,mod8,5+7i2,mod8,7+5i2,mod8.
Hence, we have2K8. For n=2t,t≥4, there are 2t−1 relatively prime numbers in Z2t, but in Z2ti, there are 22t−2 Gaussian integers. Without any loss, we take α=x+iy and γ=c+id are the two vertices; then, there will be an edge between them if and only if the congruence x+iy2≡c+id2mod2t has a solution. We can also say(6)x+iy2≡a+ibmod2k,withx,2k=1=y,2k,implies(7)x2−y2≡amod2k,2xy≡bmod2k,therefore,(8)x2+y22≡a2+b2mod2k,so,(9)N2α≡Nβmod2k,whereNα=x2+y2andNβ=a2+b2.
The number of solutions depends on the congruenceN2α≡Nβmod2k. Since Nα and Nβ are even, so after cancelation law, we have N′2α≡N′βmod2k−1 with N′β,2k−1=1. The congruence N′2α≡N′βmod2k−1 has no solution or four solutions if N′β≢1mod8 and N′β≡1mod8, respectively, by Theorem 4. There must be some residues in ℤ2k∗i which satisfies N′β≡1mod8. Thus, x+iy2≡a+ibmod2k has exactly 16 solutions. Since, the total number of residues in ℤ2k∗i is 22t−2. Hence, G˜2,2t=22t−6⋅K16,t≥4.The Gaussian quadratic residues graphG˜2,n, for n=16, is given in Figure 4.Figure 4
G˜2,16=4K16.In the following theorem, we characterize Gaussian quadratic graphsG˜2,n for the class of integers of the form n=pk, where p is a prime number of the form p≡3mod4.Theorem 10.
Ifp is a prime of the form p≡3mod4, then G˜2,pk=pk−1p−12/2K2.Proof.
Letp be a prime of the form p≡3mod4. Since the real and imaginary parts of the elements of ℤpk∗i are taken from the ring ℤpk∗, so there are pk−1p−12 number of elements in ℤpk∗i. Without any loss, assume a+ib∈ℤpk∗i with a,pk=1=b,pk, such that(10)x+iy2≡a+ibmodpk,withx,pk=1=y,pk.
This implies that(11)x2−y2≡amodpk,2xy≡bmodpk.
Therefore,(12)x2+y22≡a2+b2modpk.
Note that the congruence (12) has a solution if and only if a2+b2/p=1. Since a,p=1=b,p, so p∤a and p∤b assume that a2+b2/p=1, so there is u∈Z, such that u2≡a2+b2modp. This implies that u2−b2=u−bu+b≡a2modp. We note that u2−b2/p=u−b/pu+b/p=1 or u−b/p=u+b/p. This means that we want to show that u can be chosen, such that u−b/p=u+b/p=1. If u−b/p=u+b/p=−1, then we replace u with −u on the other side, and we get(13)−u−bp=−u+bp=−1,−1pu+bp=−1pu−bp=−1.
Since−1/p=−1p−1/2. Thus, u−b/p=u+b/p=1 if and only if p≡3mod4. Hence, x2+y22≡a2+b2modpk have exactly two solutions when p≡3mod4.Next result is the simple consequence of Theorems9 and 10.Theorem 11.
Letn=2α∏i=1kpiαi be an integer with pi≡3mod4. Then,(14)G˜2,n=K1⊗φn22kK2k,ifα=1,φn22k+2K2k+2,ifα=2,2φn22k+3K2k+3,ifα=3,22k−6φn223k−6K23k−6,ifα≥4.Theorem 12.
Letp be a prime of the form p≡1mod4; then,(15)G˜2,pk=p−124K2⊗p−128K4,ifk=1,p2p−128K4⊗pp−124K2p,ifk=2,p4p−128K4⊗pp−134K2p⊗pp−12p2−p+18K4p,ifk=3,p2k−2p−128K4⊗pp−1k4K2pk/2⊗pk−2/2p3k−4/2p−12−pp−1k8K4p,ifk≥4andk≡0mod2,p2k−2p−128K4⊗pp−1k4K2pk−1/2⊗pk−3/2p3k−1/2p−12−pp−1k8K4p,ifk≥5andk≡1mod2.Proof.
Letp be a prime number of the form p≡1mod4. Clearly, there are pk−pk−12 and 2p2k−1−p2k−2 number of units and number of zero divisors in Gaussian ring Zpki, respectively. But, the cardinality of units and zero divisors of Zp∗i=α=a+ib|a,p=1=b,p,a,b∈Zp are p−12/2. Take α, β∈Zp∗i, where α=a+ib and β=c+id. These vertices are connected to each other if and only if α2≡β2modp. Therefore, we have a2−b2≡xmodp, and 2ab≡ymodp implies a2+b22≡x2+y2modp. Thus, N2α≡Nγmodp, where Nα=a2+b2 and γ=x+iy. We discuss the following two cases:Case (I). Ifp|Nγ, then the congruence N2α≡0modp has two solutions. This means that when α and β are zero divisors, there are p−12/4 copies of K2 because the total number of zero divisors in Zp∗i is p−12/2.Case (II). Whenp∤Nγ, then the congruence N2α≡Nγmodp has four solutions. In this case, there are p−12/8 copies of K4. It is well known that if a is a unit of pk, then the congruence x2≡amodpk has four solutions. Therefore, if Nγ is a unit in Zpk∗i, then the congruence N2α≡Nγmodpk has four solutions. Thus, there are pk−2p−12/8 copies of K4 in each Zpk∗i.
Next, we discuss the number of solutions inZp2∗i for the congruence N2α≡Nγmodp2. By Theorem 3, Nγ=0; then, the congruence N2α≡0modp2 has p number of solution. Also, there are p2p−12/2 number of units in Zp2∗i, There must be pp−12/4 number of copies of K2p in Zp2∗i. Finally, we count the number of solutions of α2≡γ in Zp3∗i, while the rest of the counting in modulo pk,k≥4, can be generalized in similar fashion. If Nγ=0 or Nγ=p2, then by case (12) of Theorem 3, the congruence N2α≡Nγmodp3 has no solution. This means that there are pp−13/4 copies of K2p because there are p2p−13/2 number of elements in Zp3∗i whose norm is p2. If Nγ=p in Zp3∗i, then again by Theorem 3, we have a unique solution, but since here, we discuss solutions in Gaussian ring, so a+ib and b+ia will be treated same, that is, there are two solutions corresponding to Nγ=p in Zp3∗i, and the number of such types of elements in Zp3∗i is p2p−12p2−p+1/2. Consequently, there are p2p−12p2−p+1/8 copies of K4p.The graph ofG˜2,25 is given in Figure 5.Figure 5
G˜2,25=50K4⊗20K10.Next, result is obtained by using the result, ifx2≡amodp1α1,x2≡amodp2α2,…,x2≡amodpmαm have k1,k2,…,km number of solutions, then x2≡amodp1α1p2α2,…,pmαm has ∏i=1mki number of solutions.Theorem 13.
Letn be a positive integer. Then,(a)
Ifn=∏i=1mpi is an integer with pi≡1mod4, then G˜2,n=⊗i=0mφn2/22m+iK2m+i(b)
Ifn=∏i=1mpi2 is an integer with pi≡1mod4, then G˜2,n=φn2/23mK22m⊗i=1mpipi−12/22mK2pi(c)
Ifn=∏i=1mpi3 is an integer with pi≡1mod4, then G˜2,n=φn2/23mK22m⊗i=1mpipi−13/22mK2pi⊗i=1mpipi−12pi2−pi+1/23mK4pi(d)
Ifn=∏i=1mpik is an integer with pi≡1mod4 and k≥4 and k≡0mod2, then G˜2,n=φn2/23mK22m⊗i=1mpipi−1k/22mK2pik/2⊗i=1mpk−2/2pi3k−4/2pi−12−pipi−1k/23mK4pi(e)
Ifn=∏i=1mpik is an integer with pi≡1mod4 and k≥4 and k≡1mod2, then G˜2,n=φn2/23mK22m⊗i=1mpipi−1k/22mK2pik−1/2⊗i=1mpik−3/2pi3k−1/2pi−12−pipi−1k/23mK4piThe following result characterizes Gaussian quadratic residues graphsG˜2,n for each positive integer n.Theorem 14.
Letβ=2α×∏i=1lpiαi×∏i=1mqi×∏i=1nqi2×∏i=1rqi3×∏i=1sqik×∏i=1tqiu be a positive integer, with α≥0,αi≥0,k≥4,k≡0mod2,u≥4,u≡1mod2,pi≡3mod4,qi≡1mod4, where pi and qi are the odd primes. Then,(16)G˜2,β=∏i=1lpiαi22lK2l⊗G,ifα=0,K1⊗∏i=1lpiαi22lK2l⊗G,ifα=1,∏i=1lpiαi22l+2K2l+2⊗G,ifα=2,2×∏i=1lpiαi22l+3K2l+3⊗G,ifα=3,22l−6×∏i=1lpiαi223l−6K23l−6⊗G,ifα≥4,where(17)G=⊗i=0m∏i=1mqi222m+iK2m+i⊗φ∏i=1nqi2×∏i=1rqi3×∏i=1sqik×∏i=1tqiu223n+s+r+tK22n+s+r+t⊗i=1npipi−1222nK2pi⊗i=1rpipi−1222rK2pi⊗i=1rpipi−12pi2−pi+123rK4pi⊗i=1spk−2/2pi3k−4/2pi−12−pipi−1k23sK4pi⊗i=1spipi−1k22sK2pik/2⊗i=1tpipi−1k22tK2pik−1/2⊗i=1tpik−3/2pi3k−1/2pi−12−pipi−1k23tK4pi.


## 4. Conclusion

In this article, we discussed the mappingum≡vmmodn for m=2,3, over the unit elements of the ring of Gaussian integers and ring of integers, respectively. Furthermore, we characterized cubic and Gaussian quadratic graphs associated with the mapping um≡vm for each positive integer n in terms of complete graphs. Later on, we intend to extend our research to the zero divisors and higher values of m over various rings. We hope this work will open new doors of inquiry for other researchers and knowledge seekers in different fields.



---

*Source: 4473637-2021-12-08.xml*