On Symmetry of Complete Graphs over Quadratic and Cubic Residues

Abstract

In this study, we investigate two graphs, one of which has units of a ring $Z_n$ as vertices (or nodes) and an edge will be built between two vertices $u$ and $v$ if and only if $u^3\equiv v^3\mathrm{mod}n$. 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 $Z_{n}i$ of the form $\alpha =a+ib,\beta =c+id$, where $a,b,c,d$ are the units of $Z_n$. Two vertices $\alpha$ and $\beta$ are adjacent to each other if and only if ${\alpha }^2\equiv {\beta }^2\mathrm{mod}n$. In this piece of work, we characterize cubic and Gaussian quadratic residue graphs for each positive integer $n$ in terms of complete graphs.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 mapping $x^2⟶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 $x^n\equiv y\mathrm{mod}m$ and $x^n\equiv y^n\mathrm{mod}m$ in [12–15]. In [16], Wei and Tang introduced the concept of square mapping graphs of the Gaussian ring $Z_{n}i$. 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]).

If $p$ is a prime number of the form $p\equiv 1\mathrm{mod}3$, then the number of different cubic residues in $\mathrm{mod}p$ is $p+2/3$.

Theorem 2 (See [17]).

If $p$ is a prime of the form $p\equiv 2\mathrm{mod}3$, then there are exact $p$ cubic residues in $\mathrm{mod}p$ different from each other. In other words, all elements of $Z_p$ are cubic residues.

Theorem 3 (See [18]).

Let $p$ be a prime number and $k$ is any arbitrary positive integer. Suppose that $u$ is a solution of $fx\equiv 0\mathrm{mod}{p}^k$.

(1) If $p\mathrm{\nmid }{f}^{\prime }u$, then there is only one solution $u_{k+1}$ of $fx\equiv 0\mathrm{mod}{p}^{k+1}$, such that $u_{k+1}\equiv u\mathrm{mod}{p}^k$. The solution $u_{k+1}$ is given by $u_{k+1}=u+p^{k}v$, where $v$ is the unique solution of $f^{\prime }ut\equiv -fu/p^k\mathrm{mod}p$.

(2) If $p|f^{\prime }u$ and $p^{k+1}|fu$, then there are $p$ solutions of $fx\equiv 0\mathrm{mod}{p}^{k+1}$ that are congruent to $u$ modulo $p$, given by $u+p^{k}v$ for $v=\mathrm{0,1,2},\dots ,p-1$.

(3) If $p|f^{\prime }u$ and $p^{k+1}\mathrm{\nmid }fu$, then there are no solutions of $fx\equiv 0\mathrm{mod}{p}^{k+1}$ that are congruent to $u$ modulo $p^k$

Theorem 4 (See [19]).

Let $a$ be odd. Then, we have the following:

(1) The equation $x^2\equiv a\mathrm{mod}2$ has the unique solution $x\equiv 1\mathrm{mod}2$

(2) The equation $x^2\equiv a\mathrm{mod}4$ either has no solution if $a\equiv 3\mathrm{mod}4$ or has two solutions $x\equiv \mathrm{1,3}\mathrm{mod}4$ if $a\equiv 1\mathrm{mod}4$

(3) When $k\ge 3$, the equation $x^2\equiv a\mathrm{mod}{2}^k$ either has no solution if $a\not\equiv 1\mathrm{mod}8$ or has four solutions $x_1,-x_1,x_1+2^{k-1},-x_1+2^{k-1}$ if $a\equiv 1\mathrm{mod}8$

Definition 1 (See [20]).

Let $p$ be an odd prime and $a$ any integer. The Legendre symbol $a/p$ is defined as$$\begin{array}{}\text{(1)}& \frac{a}{p}=\begin{array}{cc}1,\hfill & \text{if\hspace{0.17em}}a\text{\hspace{0.17em}is\hspace{0.17em}quadratic\hspace{0.17em}residue\hspace{0.17em}}\mathrm{mod}p,\hfill \\ 0,\hfill & p|a,\hfill \\ -1,\hfill & \text{if\hspace{0.17em}}a\text{\hspace{0.17em}is\hspace{0.17em}quadratic\hspace{0.17em}nonresidue\hspace{0.17em}}\mathrm{mod}p.\hfill \end{array}\end{array}$$

2. Cubic Residues Graphs

In this section, we elaborate the concept of cubic residue graph and then characterize these graphs completely for each positive integer $n$. The disjoint union of the graphs $H$ and $K$ is expressed by $H\oplus K$, and the disjoint union of the $n$ copies of the graph $K$ is denoted as $nK=K\oplus K\oplus \cdots \oplus K$.

Definition 2.

Let $n$ be a positive integer. A simple graph $\widehat{G}3,n$ is said to be cubic residue graph if the vertex set of the graph $\widehat{G}3,n$ is $V\widehat{G}3,n=v\in Z^{+}|v,n=1\text{\hspace{0.17em}and\hspace{0.17em}}v<n$ and the edge set of $\widehat{G}3,n$ is $E\widehat{G}3,n=uv|u,v\in V\widehat{G}3,n\text{\hspace{0.17em}and\hspace{0.17em}}{u}^3\equiv v^3\mathrm{mod}n$.

Example 1.

For $n=27$, the vertex set of $\widehat{G}\mathrm{3,27}$ is $\mathrm{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26}$. We can easily see that $1^3\equiv {10}^3\equiv {19}^3\equiv 1\mathrm{mod}27$, $2^3\equiv {11}^3\equiv {20}^3\equiv 8\mathrm{mod}27$, $4^3\equiv {13}^3\equiv {22}^3\equiv 10\mathrm{mod}27$, $5^3\equiv {14}^3\equiv {23}^3\equiv 17\mathrm{mod}27$, $7^3\equiv {16}^3\equiv {25}^3\equiv 19\mathrm{mod}27$, and $8^3\equiv {17}^3\equiv {26}^3\equiv 26\mathrm{mod}27$. $\widehat{G}\mathrm{3,27}=6K_3$ is shown in Figure 1.

[figure omitted; refer to PDF]

In the following result, we characterize cubic residues graphs for the class of integers of the form $2^k$ and $p^k$, where $p$ is an odd prime.

Theorem 5.

Let $\widehat{G}3,n$ be a cubic residue graph. Then,

(a) The graph $\widehat{G}3,n,k\ge 1$ is empty

(b) If $p\equiv 5\mathrm{mod}6$, then the graph $\widehat{G}3,p^k,k\ge 1$ is empty

(c) If $p\equiv 1\mathrm{mod}6$, then $\widehat{G}3,p^k=p^{k-1}p-1/3K_3,k\ge 1$

(d) The graph $\widehat{G}3,3^k=2\cdot 3^{k-2}{K}_3,k\ge 2$

Proof.

(a) Let $n=2^k,k\ge 1$ be an integer. The distinct vertices $a$ and $b$ are adjacent only when congruence $a^3\equiv b^3\mathrm{mod}{2}^k$ has a solution, where $a,b\in Z_{2^k}$ with $a,2^k=1=b,2^k$. The congruence $a^3\equiv b^3\mathrm{mod}{2}^k$ implies $a^3-b^3=a-b{a}^2+ab+b^2\equiv 0\mathrm{mod}{2}^k$. Thus, $a\equiv b\mathrm{mod}{2}^k$ or $a^2+ab+b^2\equiv 0\mathrm{mod}{2}^k$. Both congruence show that there does not exists any integer $a$ and $b$ from $Z_{2^k}$, with $a,2^k=1=b,2^k$, such that the congruence $a^3\equiv b^3\mathrm{mod}{2}^k$ has a solution. Thus, $\widehat{G}3,2^k,k\ge 1$ is empty graph.

(b) Since, $p=5\mathrm{mod}6$ implies $p=2\mathrm{mod}3$. Thus, by Theorem 1, all cubic residues of $\mathrm{mod}{p}^k,k\ge 1$ are different; therefore, graph $\widehat{G}3,p^k,k\ge 1$ with $p\equiv 1\mathrm{mod}6$ is empty.

(c) By Theorem 2, the number of nonzero different cubic residues of $\mathrm{mod}{p}^k$ is $p^{k-1}p-1/3$. Thus, $\widehat{G}3,p^k=p^{k-1}p-1/3K_3,k\ge 1$.

(d) An integer $a$ is a cubic residue of $\mathrm{mod}{3}^k$ if and only if the congruence $x^3\equiv a\mathrm{mod}{3}^k$ is solvable, and in this case, the cubic residues are different only if $x$ belongs to the set $S=\mathrm{1,2,4,5,7},\dots ,3^{k-1}-2,3^{k-1}-1$. The cardinality of the set $S$ is $2\cdot 3^{k-2}$. The proof is done if we show exactly two more residues that are relatively prime to $3^k$ other than from the element of $S$.

$$\begin{array}{c}\text{(2)}& 1^3\equiv \begin{array}{c}1=1^3\mathrm{mod}{3}^k\hfill \\ 1=1+3^{3k-3}+3^{k}1+3^{k-1}={1+3^{k-1}}^3\mathrm{mod}{3}^k\hfill \\ 1=1+2^3\cdot 3^{3k-3}+2\cdot 3^{k}1+2\cdot 3^{k-1}={1+2\cdot 3^{k-1}}^3\mathrm{mod}{3}^k\hfill \end{array}{2}^3\equiv \begin{array}{c}8=2^3\mathrm{mod}{3}^k\hfill \\ 8=2^3+3^{3k-3}+2\cdot 3^{k}1+3^{k-1}={2+3^{k-1}}^3\mathrm{mod}{3}^k\hfill \\ 8=2^3+2^3\cdot 3^{3k-3}+4\cdot 3^{k}2+2\cdot 3^{k-1}={2+2\cdot 3^{k-1}}^3\mathrm{mod}{3}^k\hfill \end{array}\\ 4^3\equiv \begin{array}{c}64=4^3\mathrm{mod}{3}^k\hfill \\ 64={1+31+3^{k-2}}^3=1+3^3{1+3^{k-2}}^3+3^{2}1+3^{k-2}1+31+3^{k-2}\mathrm{mod}{3}^k\hfill \\ 64={1+31+2\cdot 3^{k-2}}^3=1+3^3{1+2\cdot 3^{k-2}}^3+3^{2}1+2\cdot 3^{k-2}1+31+2\cdot 3^{k-2}\mathrm{mod}{3}^k\hfill \end{array}\\ ⋮\\ {3^{k-1}-2}^3\equiv \begin{array}{c}-8\mathrm{mod}{3}^k\hfill \\ -8={2\cdot 3^{k-1}-2}^3=-8+2^3\cdot 3^{3k-3}-3\cdot 4\cdot 3^{k-1}2\cdot 3^{k-1}-2\mathrm{mod}{3}^k\hfill \\ -8={3\cdot 3^{k-1}-2}^3=-8+3^{3k}-2\cdot 3^{k+1}3\cdot 3^{k-1}-2\mathrm{mod}{3}^k\hfill \end{array}\\ {3^{k-1}-1}^3\equiv \begin{array}{c}-1\mathrm{mod}{3}^k,\hfill \\ -1={2\cdot 3^{k-1}-1}^3=-1+3^{3k-3}-3\cdot 2\cdot 3^{k-1}2\cdot 3^{k-1}-1\mathrm{mod}{3}^k,\hfill \\ -1={3\cdot 3^{k-1}-1}^3=-1+3^{3k}-3^{k+1}3\cdot 3^{k-1}-1\mathrm{mod}{3}^k.\hfill \end{array}\end{array}$$

Hence, the reduced residue system of $Z_{3^k},k\ge 2$ has exactly $2\cdot 3^{k-2}$ nonzero cubic residues. Thus, graph $\widehat{G}3,3^k$ is $2\cdot 3^{k-2}{K}_3$.

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.

If $m=3\cdot 2^{\alpha }\cdot {\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}$, $\alpha$ and ${\beta }_i\ge 1$ with each $p_i\equiv 5\mathrm{mod}6$, then $\widehat{G}3,m$ is empty.

Proof.

Let $m=3\cdot 2^{\alpha }\cdot {\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}$ be an integer, with $\alpha$ and ${\beta }_i\ge 1$ and $p_i\equiv 5\mathrm{mod}6$. By Theorem 2, all cubic residues of $Z_3$, $Z_{2^{\alpha }}$, and $Z_{{\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}}$ are different. Since 3, $2^{\alpha }$, and ${\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}$ are relatively prime to each other, so no residues of $Z_m$ are connected to each other. Thus, graph $\widehat{G}3,m$ is empty.

Theorem 7.

If $m={\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}$ and ${\beta }_i\ge 1$ with each $p_i\equiv 1\mathrm{mod}6$, then $\widehat{G}3,m=\phi m/3^r{K}_{3^r}$.

Proof.

Let $m={\displaystyle {\prod }_{i=1}^r{p}_i^{{\beta }_i}}$, and ${\beta }_i\ge 1$ be an integer with each $p_i\equiv 1\mathrm{mod}6$. Since each $p_i\equiv 1\mathrm{mod}6$, so by Theorem 1, the number of nonzero distinct cubic residues in $\mathrm{mod}p$ is $p-1/3$ and thus in $\mathrm{mod}m$ is $\phi m/3^r$. Therefore, by Chinese reminder theorem (CRT), the reduced residue system of $Z_m$ has $3^r$ number of distinct solutions. Hence, $\widehat{G}3,m=\phi m/3^r{K}_{3^r}$.

The coming result is the main result of this section that characterizes cubic residue graph for each positive integer $n$.

Theorem 8.

If $m=2^{\alpha }\cdot 3^{\beta }\cdot {\displaystyle {\prod }_{i=1}^r{p}_i^{{\alpha }_i}}\cdot {\displaystyle {\prod }_{j=1}^s{q}_j^{{\beta }_j}}$, ${\alpha }_i,{\beta }_j\ge 1$, with each $p_i\equiv 1\mathrm{mod}6$ and $q_j\equiv 5\mathrm{mod}6$, then$$\begin{array}{}\text{(3)}& \widehat{G}3,m=\begin{array}{cc}\frac{\phi m}{3^r}{K}_{3^r},\hfill & \text{if\hspace{0.17em}}\alpha \ge 0,\beta =0\text{\hspace{0.17em}or\hspace{0.17em}}1,\hfill \\ \frac{\phi m}{3^{r+1}}{K}_{3^{r+1}},\hfill & \text{if\hspace{0.17em}}\alpha \ge 0,\beta \ge 2.\hfill \end{array}\end{array}$$

Proof.

Let $m=2^{\alpha }\cdot 3^{\beta }\cdot {\displaystyle {\prod }_{i=1}^r{p}_i^{{\alpha }_i}}\cdot {\displaystyle {\prod }_{j=1}^s{q}_j^{{\beta }_j}}$, ${\alpha }_i,{\beta }_j\ge 1$ with each $p_i\equiv 1\mathrm{mod}6$, and $q_j\equiv 5\mathrm{mod}6$. When $\alpha \ge 0,\beta =0$ or 1, then proof is done by Theorem 5, and when $\alpha \ge 0,\beta \ge 2$, by using CRT and Theorem 5 part (c) and (d), we have Theorem 8.

The cubic residues graph for $n=91$ is shown in Figure 2.

[figure omitted; refer to PDF]

The following theorem characterizes Gaussian quadratic residues graphs $\tilde{G}2,n$ for the class of integers of the form $n=2^t$, where $t$ is a positive integer.

Theorem 9.

Let $n$ be an integer; then,$$\begin{array}{}\text{(4)}& \tilde{G}2,n=\begin{array}{cc}{K}_1,\hfill & \text{if\hspace{0.17em}}n=2,\hfill \\ K_4,\hfill & \text{if\hspace{0.17em}}n=2^2,\hfill \\ 2\cdot K_8,\hfill & \text{if\hspace{0.17em}}n=2^3,\hfill \\ 2^{2t-6}\cdot K_{16},\hfill & \text{if\hspace{0.17em}}n=2^t,t\ge 4.\hfill \end{array}\end{array}$$

Proof.

Let $n=2$ be an integer; then, the vertex set has only one element, namely, $1+i$, so $\tilde{G}2,n$ is empty. If $n=2^4$, then the vertex set of $\tilde{G}2,2^2$ is $1+i,3+i,1+3i,3+3i$, clearly ${1+i}^2\equiv {1+3i}^2\equiv {3+i}^2\equiv {3+3i}^2\equiv 2i\mathrm{mod}4$. Thus, each vertex of $\tilde{G}2,2^2$ are connected to each other; hence, we have $K_4$. For $n=2^3$, the vertex set of $\tilde{G}2,2^3$ 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,$$\begin{array}{c}\text{(5)}& 2i\equiv \begin{array}{cc}{1+i}^2,\hfill & \mathrm{mod}8,\hfill \\ {1+5i}^2,\hfill & \mathrm{mod}8,\hfill \\ {5+i}^2,\hfill & \mathrm{mod}8,\hfill \\ {3+3i}^2,\hfill & \mathrm{mod}8,\hfill \\ {3+7i}^2,\hfill & \mathrm{mod}8,\hfill \\ {7+3i}^2,\hfill & \mathrm{mod}8,\hfill \\ {5+5i}^2,\hfill & \mathrm{mod}8,\hfill \\ {7+7i}^2,\hfill & \mathrm{mod}8,\hfill \end{array},6i\equiv \begin{array}{cc}{1+3i}^2,\hfill & \mathrm{mod}8,\hfill \\ {3+i}^2,\hfill & \mathrm{mod}8,\hfill \\ {1+7i}^2,\hfill & \mathrm{mod}8,\hfill \\ {7+i}^2,\hfill & \mathrm{mod}8,\hfill \\ {3+5i}^2,\hfill & \mathrm{mod}8,\hfill \\ {5+3i}^2,\hfill & \mathrm{mod}8,\hfill \\ {5+7i}^2,\hfill & \mathrm{mod}8,\hfill \\ {7+5i}^2,\hfill & \mathrm{mod}8.\hfill \end{array}\end{array}$$

Hence, we have $2K_8$. For $n=2^t,t\ge 4$, there are $2^{t-1}$ relatively prime numbers in $Z_{2^t}$, but in $Z_{2^t}i$, there are $2^{2t-2}$ Gaussian integers. Without any loss, we take $\alpha =x+iy$ and $\gamma =c+id$ are the two vertices; then, there will be an edge between them if and only if the congruence ${x+iy}^2\equiv {c+id}^2\mathrm{mod}{2}^t$ has a solution. We can also say$$\begin{array}{}\text{(6)}& {x+iy}^2\equiv a+ib\mathrm{mod}{2}^k,\hspace{1em}\text{with\hspace{0.17em}}x,2^k=1=y,2^k,\end{array}$$implies$$\begin{array}{c}\text{(7)}& x^2-y^2\equiv a\mathrm{mod}{2}^k,2xy\equiv b\mathrm{mod}{2}^k,\end{array}$$therefore,$$\begin{array}{}\text{(8)}& {x^2+y^2}^2\equiv a^2+b^2\mathrm{mod}{2}^k,\end{array}$$so,$$\begin{array}{}\text{(9)}& N^2\alpha \equiv N\beta \mathrm{mod}{2}^k,\hspace{1em}\text{where\hspace{0.17em}}N\alpha =x^2+y^2\text{\hspace{0.17em}and\hspace{0.17em}}N\beta =a^2+b^2.\end{array}$$

The number of solutions depends on the congruence $N^2\alpha \equiv N\beta \mathrm{mod}{2}^k$. Since $N\alpha$ and $N\beta$ are even, so after cancelation law, we have $N^{\prime 2}\alpha \equiv N^{\prime }\beta \mathrm{mod}{2}^{k-1}$ with $N^{\prime }\beta ,2^{k-1}=1$. The congruence $N^{\prime 2}\alpha \equiv N^{\prime }\beta \mathrm{mod}{2}^{k-1}$ has no solution or four solutions if $N^{\prime }\beta \not\equiv 1\mathrm{mod}8$ and $N^{\prime }\beta \equiv 1\mathrm{mod}8$, respectively, by Theorem 4. There must be some residues in ${\mathbb{Z}}_{2^k}^{\ast }i$ which satisfies $N^{\prime }\beta \equiv 1\mathrm{mod}8$. Thus, ${x+iy}^2\equiv a+ib\mathrm{mod}{2}^k$ has exactly 16 solutions. Since, the total number of residues in ${\mathbb{Z}}_{2^k}^{\ast }i$ is $2^{2t-2}$. Hence, $\tilde{G}2,2^t=2^{2t-6}\cdot K_{16},t\ge 4$.

The Gaussian quadratic residues graph $\tilde{G}2,n$, for $n=16$, is given in Figure 4.

[figure omitted; refer to PDF]

In the following theorem, we characterize Gaussian quadratic graphs $\tilde{G}2,n$ for the class of integers of the form $n=p^k$, where $p$ is a prime number of the form $p\equiv 3\mathrm{mod}4$.

Theorem 10.

If $p$ is a prime of the form $p\equiv 3\mathrm{mod}4$, then $\tilde{G}2,p^k={p^{k-1}p-1}^2/2K_2$.

Proof.

Let $p$ be a prime of the form $p\equiv 3\mathrm{mod}4$. Since the real and imaginary parts of the elements of ${\mathbb{Z}}_{p^k}^{\ast }i$ are taken from the ring ${\mathbb{Z}}_{p^k}^{\ast }$, so there are ${p^{k-1}p-1}^2$ number of elements in ${\mathbb{Z}}_{p^k}^{\ast }i$. Without any loss, assume $a+ib\in {\mathbb{Z}}_{p^k}^{\ast }i$ with $a,p^k=1=b,p^k$, such that$$\begin{array}{}\text{(10)}& {x+iy}^2\equiv a+ib\mathrm{mod}{p}^k,\hspace{1em}\text{with\hspace{0.17em}}x,p^k=1=y,p^k.\end{array}$$

This implies that$$\begin{array}{c}\text{(11)}& x^2-y^2\equiv a\mathrm{mod}{p}^k,2xy\equiv b\mathrm{mod}{p}^k.\end{array}$$

Therefore,$$\begin{array}{}\text{(12)}& {x^2+y^2}^2\equiv a^2+b^2\mathrm{mod}{p}^k.\end{array}$$

Note that the congruence (12) has a solution if and only if $a^2+b^2/p=1$. Since $a,p=1=b,p$, so $p\mathrm{\nmid }a$ and $p\mathrm{\nmid }b$ assume that $a^2+b^2/p=1$, so there is $u\in Z$, such that $u^2\equiv a^2+b^2\mathrm{mod}p$. This implies that $u^2-b^2=u-bu+b\equiv a^2\mathrm{mod}p$. We note that $u^2-b^2/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$$\begin{array}{c}\text{(13)}& \frac{-u-b}{p}=\frac{-u+b}{p}=-1,\frac{-1}{p}\frac{u+b}{p}=\frac{-1}{p}\frac{u-b}{p}=-1.\end{array}$$

Since $-1/p={-1}^{p-1/2}$. Thus, $u-b/p=u+b/p=1$ if and only if $p\equiv 3\mathrm{mod}4$. Hence, ${x^2+y^2}^2\equiv a^2+b^2\mathrm{mod}{p}^k$ have exactly two solutions when $p\equiv 3\mathrm{mod}4$.

Next result is the simple consequence of Theorems 9 and 10.

Theorem 11.

Let $n=2^{\alpha }{\displaystyle {\prod }_{i=1}^k{p}_i^{{\alpha }_i}}$ be an integer with $p_i\equiv 3\mathrm{mod}4$. Then,$$\begin{array}{}\text{(14)}& \tilde{G}2,n=\begin{array}{cc}{K}_1\otimes \frac{{\phi n}^2}{2^k}{K}_{2^k},\hfill & \text{if\hspace{0.17em}}\alpha =1,\hfill \\ \frac{{\phi n}^2}{2^{k+2}}{K}_{2^{k+2}},\hfill & \text{if\hspace{0.17em}}\alpha =2,\hfill \\ 2\frac{{\phi n}^2}{2^{k+3}}{K}_{2^{k+3}},\hfill & \text{if\hspace{0.17em}}\alpha =3,\hfill \\ 2^{2k-6}\frac{{\phi n}^2}{2^{3k-6}}{K}_{2^{3k-6}},\hfill & \text{if\hspace{0.17em}}\alpha \ge 4.\hfill \end{array}\end{array}$$

Theorem 12.

Let $p$ be a prime of the form $p\equiv 1\mathrm{mod}4$; then,$$\begin{array}{}\text{(15)}& \tilde{G}2,p^k=\begin{array}{cc}\frac{{p-1}^2}{4}{K}_2\otimes \frac{{p-1}^2}{8}{K}_4,\hfill & \text{if\hspace{0.17em}}k=1,\hfill \\ \frac{p^2{p-1}^2}{8}{K}_4\otimes \frac{p{p-1}^2}{4}{K}_{2p},\hfill & \text{if\hspace{0.17em}}k=2,\hfill \\ \frac{p^4{p-1}^2}{8}{K}_4\otimes \frac{p{p-1}^3}{4}{K}_{2p}\otimes \frac{p{p-1}^2{p}^2-p+1}{8}{K}_{4p},\hfill & \text{if\hspace{0.17em}}k=3,\hfill \\ \frac{p^{2k-2}{p-1}^2}{8}{K}_4\otimes \frac{p{p-1}^k}{4}{K}_{2p^{k/2}}\otimes \frac{p^{k-2/2}{p}^{3k-4/2}{p-1}^2-p{p-1}^k}{8}{K}_{4p},\hfill & \text{if\hspace{0.17em}}k\ge 4\text{\hspace{0.17em}and\hspace{0.17em}}k\equiv 0\mathrm{mod}2,\hfill \\ \frac{p^{2k-2}{p-1}^2}{8}{K}_4\otimes \frac{p{p-1}^k}{4}{K}_{2p^{k-1/2}}\otimes \frac{p^{k-3/2}{p}^{3k-1/2}{p-1}^2-p{p-1}^k}{8}{K}_{4p},\hfill & \text{if\hspace{0.17em}}k\ge 5\text{\hspace{0.17em}and\hspace{0.17em}}k\equiv 1\mathrm{mod}2.\hfill \end{array}\end{array}$$

Proof.

Let $p$ be a prime number of the form $p\equiv 1\mathrm{mod}4$. Clearly, there are ${p^k-p^{k-1}}^2$ and $2p^{2k-1}-p^{2k-2}$ number of units and number of zero divisors in Gaussian ring $Z_{p^k}i$, respectively. But, the cardinality of units and zero divisors of $Z_p^{\ast }i=\alpha =a+ib|a,p=1=b,p,a,b\in Z_p$ are ${p-1}^2/2$. Take $\alpha$, $\beta \in Z_p^{\ast }i$, where $\alpha =a+ib$ and $\beta =c+id$. These vertices are connected to each other if and only if ${\alpha }^2\equiv {\beta }^2\mathrm{mod}p$. Therefore, we have $a^2-b^2\equiv x\mathrm{mod}p$, and $2ab\equiv y\mathrm{mod}p$ implies ${a^2+b^2}^2\equiv x^2+y^2\mathrm{mod}p$. Thus, $N^2\alpha \equiv N\gamma \mathrm{mod}p$, where $N\alpha =a^2+b^2$ and $\gamma =x+iy$. We discuss the following two cases:

  Case (I). If $p|N\gamma$, then the congruence $N^2\alpha \equiv 0\mathrm{mod}p$ has two solutions. This means that when $\alpha$ and $\beta$ are zero divisors, there are ${p-1}^2/4$ copies of $K_2$ because the total number of zero divisors in $Z_p^{\ast }i$ is ${p-1}^2/2$.

  Case (II). When $p\mathrm{\nmid }N\gamma$, then the congruence $N^2\alpha \equiv N\gamma \mathrm{mod}p$ has four solutions. In this case, there are ${p-1}^2/8$ copies of $K_4$. It is well known that if $a$ is a unit of $p^k$, then the congruence $x^2\equiv a\mathrm{mod}{p}^k$ has four solutions. Therefore, if $N\gamma$ is a unit in $Z_{p^k}^{\ast }i$, then the congruence $N^2\alpha \equiv N\gamma \mathrm{mod}{p}^k$ has four solutions. Thus, there are $p^{k-2}{p-1}^2/8$ copies of $K_4$ in each $Z_{p^k}^{\ast }i$.

Next, we discuss the number of solutions in $Z_{p^2}^{\ast }i$ for the congruence $N^2\alpha \equiv N\gamma \mathrm{mod}{p}^2$. By Theorem 3, $N\gamma =0$; then, the congruence $N^2\alpha \equiv 0\mathrm{mod}{p}^2$ has $p$ number of solution. Also, there are $p^2{p-1}^2/2$ number of units in $Z_{p^2}^{\ast }i$, There must be $p{p-1}^2/4$ number of copies of $K_{2p}$ in $Z_{p^2}^{\ast }i$. Finally, we count the number of solutions of ${\alpha }^2\equiv \gamma$ in $Z_{p^3}^{\ast }i$, while the rest of the counting in modulo $p^k,k\ge 4$, can be generalized in similar fashion. If $N\gamma =0$ or $N\gamma =p^2$, then by case (12) of Theorem 3, the congruence $N^2\alpha \equiv N\gamma \mathrm{mod}{p}^3$ has no solution. This means that there are $p{p-1}^3/4$ copies of $K_{2p}$ because there are $p^2{p-1}^3/2$ number of elements in $Z_{p^3}^{\ast }i$ whose norm is $p^2$. If $N\gamma =p$ in $Z_{p^3}^{\ast }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\gamma =p$ in $Z_{p^3}^{\ast }i$, and the number of such types of elements in $Z_{p^3}^{\ast }i$ is $p^2{p-1}^2{p}^2-p+1/2$. Consequently, there are $p^2{p-1}^2{p}^2-p+1/8$ copies of $K_{4p}$.

The graph of $\tilde{G}\mathrm{2,25}$ is given in Figure 5.

[figure omitted; refer to PDF]

Next, result is obtained by using the result, if $x^2\equiv a\mathrm{mod}{p}_1^{{\alpha }_1},x^2\equiv a\mathrm{mod}{p}_2^{{\alpha }_2},\dots ,x^2\equiv a\mathrm{mod}{p}_m^{{\alpha }_m}$ have $k_1,k_2,\dots ,k_m$ number of solutions, then $x^2\equiv a\mathrm{mod}{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2},\dots ,p_m^{{\alpha }_m}$ has ${\displaystyle {\prod }_{i=1}^m{k}_i}$ number of solutions.

Theorem 13.

Let $n$ be a positive integer. Then,

(a) If $n={\displaystyle {\prod }_{i=1}^m{p}_i}$ is an integer with $p_i\equiv 1\mathrm{mod}4$, then $\tilde{G}2,n={\otimes }_{i=0}^m{\phi n}^2/2^{2m+i}{K}_{2^{m+i}}$

(b) If $n={\displaystyle {\prod }_{i=1}^m{p}_i^2}$ is an integer with $p_i\equiv 1\mathrm{mod}4$, then $\tilde{G}2,n={\phi n}^2/2^{3m}{K}_{2^{2m}}{\otimes }_{i=1}^m{p}_i{p_i-1}^2/2^{2m}{K}_{2p_i}$

(c) If $n={\displaystyle {\prod }_{i=1}^m{p}_i^3}$ is an integer with $p_i\equiv 1\mathrm{mod}4$, then $\tilde{G}2,n={\phi n}^2/2^{3m}{K}_{2^{2m}}{\otimes }_{i=1}^m{p}_i{p_i-1}^3/2^{2m}{K}_{2p_i}{\otimes }_{i=1}^m{p}_i{p_i-1}^2{p}_i^2-p_i+1/2^{3m}{K}_{4p_i}$

(d) If $n={\displaystyle {\prod }_{i=1}^m{p}_i^k}$ is an integer with $p_i\equiv 1\mathrm{mod}4$ and $k\ge 4$ and $k\equiv 0\mathrm{mod}2$, then $\tilde{G}2,n={\phi n}^2/2^{3m}{K}_{2^{2m}}{\otimes }_{i=1}^m{p}_i{p_i-1}^k/2^{2m}{K}_{2p_i^{k/2}}{\otimes }_{i=1}^m{p}^{k-2/2}{p}_i^{3k-4/2}{p_i-1}^2-p_i{p_i-1}^k/2^{3m}{K}_{4p_i}$

(e) If $n={\displaystyle {\prod }_{i=1}^m{p}_i^k}$ is an integer with $p_i\equiv 1\mathrm{mod}4$ and $k\ge 4$ and $k\equiv 1\mathrm{mod}2$, then $\tilde{G}2,n={\phi n}^2/2^{3m}{K}_{2^{2m}}{\otimes }_{i=1}^m{p}_i{p_i-1}^k/2^{2m}{K}_{2p_i^{k-1/2}}{\otimes }_{i=1}^m{p}_i^{k-3/2}{p}_i^{3k-1/2}{p_i-1}^2-p_i{p_i-1}^k/2^{3m}{K}_{4p_i}$

The following result characterizes Gaussian quadratic residues graphs $\tilde{G}2,n$ for each positive integer $n$.

Theorem 14.

Let $\beta =2^{\alpha }\times {\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}\times {\displaystyle {\prod }_{i=1}^m{q}_i}\times {\displaystyle {\prod }_{i=1}^n{q}_i^2}\times {\displaystyle {\prod }_{i=1}^r{q}_i^3}\times {\displaystyle {\prod }_{i=1}^s{q}_i^k}\times {\displaystyle {\prod }_{i=1}^t{q}_i^u}$ be a positive integer, with $\alpha \ge 0,{\alpha }_i\ge 0,k\ge 4,k\equiv 0\mathrm{mod}2,u\ge 4,u\equiv 1\mathrm{mod}2,p_i\equiv 3\mathrm{mod}4,q_i\equiv 1\mathrm{mod}4$, where $p_i$ and $q_i$ are the odd primes. Then,$$\begin{array}{}\text{(16)}& \tilde{G}2,\beta =\begin{array}{cc}\frac{{{\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}}^2}{2^l}{K}_{2^l}\otimes G,\hfill & \text{if\hspace{0.17em}}\alpha =0,\hfill \\ K_1\otimes \frac{{{\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}}^2}{2^l}{K}_{2^l}\otimes G,\hfill & \text{if\hspace{0.17em}}\alpha =1,\hfill \\ \frac{{{\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}}^2}{2^{l+2}}{K}_{2^{l+2}}\otimes G,\hfill & \text{if\hspace{0.17em}}\alpha =2,\hfill \\ 2\times \frac{{{\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}}^2}{2^{l+3}}{K}_{2^{l+3}}\otimes G,\hfill & \text{if\hspace{0.17em}}\alpha =3,\hfill \\ 2^{2l-6}\times \frac{{{\displaystyle {\prod }_{i=1}^l{p}_i^{{\alpha }_i}}}^2}{2^{3l-6}}{K}_{2^{3l-6}}\otimes G,\hfill & \text{if\hspace{0.17em}}\alpha \ge 4,\hfill \end{array}\end{array}$$where$$\begin{array}{c}\text{(17)}& G=\underset{i=0}{\overset{m}{\otimes }}\frac{{{\displaystyle {\prod }_{i=1}^m{q}_i}}^2}{2^{2m+i}}{K}_{2^{m+i}}\otimes \frac{\phi {{\displaystyle {\prod }_{i=1}^n{q}_i^2}\times {\displaystyle {\prod }_{i=1}^r{q}_i^3}\times {\displaystyle {\prod }_{i=1}^s{q}_i^k}\times {\displaystyle {\prod }_{i=1}^t{q}_i^u}}^2}{2^{3n+s+r+t}}{K}_{2^{2n+s+r+t}}\underset{i=1}{\overset{n}{\otimes }}\frac{p_i{p_i-1}^2}{2^{2n}}{K}_{2p_i}\underset{i=1}{\overset{r}{\otimes }}\frac{p_i{p_i-1}^2}{2^{2r}}{K}_{2p_i}\underset{i=1}{\overset{r}{\otimes }}\frac{p_i{p_i-1}^2{p}_i^2-p_i+1}{2^{3r}}{K}_{4p_i}\underset{i=1}{\overset{s}{\otimes }}\frac{p^{k-2/2}{p}_i^{3k-4/2}{p_i-1}^2-p_i{p_i-1}^k}{2^{3s}}{K}_{4p_i}\\ \underset{i=1}{\overset{s}{\otimes }}\frac{p_i{p_i-1}^k}{2^{2s}}{K}_{2p_i^{k/2}}\underset{i=1}{\overset{t}{\otimes }}\frac{p_i{p_i-1}^k}{2^{2t}}{K}_{2p_i^{k-1/2}}\underset{i=1}{\overset{t}{\otimes }}\frac{p_i^{k-3/2}{p}_i^{3k-1/2}{p_i-1}^2-p_i{p_i-1}^k}{2^{3t}}{K}_{4p_i}.\end{array}$$

4. Conclusion

In this article, we discussed the mapping $u^m\equiv v^m\mathrm{mod}n$ for $m=\mathrm{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 $u^m\equiv v^m$ 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.

Acknowledgments

This research work was supported by the National University of Modern Languages, Lahore, Pakistan.

References

[1] N. Deo, Graph Theory with Applications to Engineering and Computer Science, 2017.

[2] N. Jafarzadeh, A. Iranmanesh, "Application of graph theory to biological problems," Studia Ubb Chemia, vol. 61, 2016.

[3] A. T. Balaban, "Applications of graph theory in chemistry," Journal of Chemical Information and Computer Sciences, vol. 25 no. 3, pp. 334-343, DOI: 10.1021/ci00047a033, 1985.

[4] F. Dorfler, F. Bullo, "Kron reduction of graphs with applications to electrical networks," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 60 no. 1, pp. 150-163, DOI: 10.1109/tcsi.2012.2215780, 2013.

[5] K. Balasubramanian, "Graph theoretical perception of molecular symmetry," Chemical Physics Letters, vol. 232 no. 5-6, pp. 415-423, DOI: 10.1016/0009-2614(94)01382-6, 1995.

[6] N. Abbas, S. Nadeem, M. Y. Malik, "Theoretical study of micropolar hybrid nanofluid over Riga channel with slip conditions," Physica A: Statistical Mechanics and Its Applications, vol. 551,DOI: 10.1016/j.physa.2019.124083, 2020.

[7] N. Abbas, S. Nadeem, A. Saleem, M. Y. Malik, A. Issakhov, F. M. Alharbi, "Models base study of inclined MHD of hybrid nanofluid flow over nonlinear stretching cylinder," Chinese Journal of Physics, vol. 69, pp. 109-117, DOI: 10.1016/j.cjph.2020.11.019, 2021.

[8] T. D. Rogers, "The graph of the square mapping on the prime fields," Discrete Mathematics, vol. 148 no. 1-3, pp. 317-324, DOI: 10.1016/0012-365x(94)00250-m, 1996.

[9] L. Somer, M. Křížek, "Structure of digraphs associated with quadratic congruences with composite moduli," Discrete Mathematics, vol. 306 no. 18, pp. 2174-2185, DOI: 10.1016/j.disc.2005.12.026, 2006.

[10] M. K. Mahmood, F. Ahmad, "An informal enumeration of squares of 2 k using rooted trees arising from congruences," Utilitas Mathematica, vol. 105, pp. 41-51, 2017.

[11] M. K. Mahmood, F. Ahmad, "A classification of cyclic nodes and enumeration of components of a class of discrete graphs," Applied Mathematics & Information Sciences, vol. 9 no. 1, pp. 103-112, DOI: 10.12785/amis/090115, 2015.

[12] M. H. Mateen, M. K. Mahmood, "Power digraphs associated with the congruence x n ≡ y mod   m," Punjab University Journal of Mathematics, vol. 51, pp. 93-102, 2019.

[13] M. H. Mateen, M. K. Mahmmod, M. K. Mahmmod, D. Alghazzawi, J.-B. Liu, "Structures of power digraphs over the congruence equation $ x^p\equiv y\; (\text{mod}\; m) $ and enumerations," AIMS Mathematics, vol. 6 no. 5, pp. 4581-4596, DOI: 10.3934/math.2021270, 2021.

[14] M. H. Mateen, M. K. Mahmood, "A new approch for the enumeration of components of digraphs over the quadratic maps," Journal of Prime Research in Mathematics, vol. 16, pp. 56-66, 2020.

[15] M. H. Mateen, M. K. Mahmood, S. Ali, "Importance of power digraph in computer science," Proceedings of the 2019 International Conference on Innovative Computing (ICIC), .

[16] Yang-Jiang, T. Gao-Hua, "The square mapping graphs of the ring Z n i," Journal of Mathematics, vol. 36, 2016.

[17] D. Namli, "Some results on cubic residues," International Journal of Algebra, vol. 9, pp. 245-249, DOI: 10.12988/ija.2015.5525, 2015.

[18] A. Adler, J. Coury, The Theory of Numbers, 1995.

[19] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, 1990.

[20] G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 1980.