# On Simple Graphs Arising from Exponential Congruences

Authors: M. Aslam Malik; M. Khalid Mahmood
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integersa and b, let G(n) denote the graph for which V={0,1,…,n−1} is the set of vertices and there is an edge between a and b if the congruence ax≡b(modn) is solvable. Let n=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes. The number of nontrivial self-loops of the graph G(n) has been determined and shown to be equal to ∏i=1r(ϕ(piki)+1). It is shown that the graph G(n) has 2r components. Further, it is proved that the component Γp of the simple graph G(p2) is a tree with root at zero, and if n is a Fermat's prime, then the component Γϕ(n) of the simple graph G(n) is complete.


---

## Body

## 1. Introduction

The notion of congruence is intrinsic in number theory. Modular arithmetic has clutched a vital contrivance for most of the number theoretic mathematics. In recent years, studying graphs through congruences is of charismatic and an independent interest of number theorists. It has cemented a novel approach to introduce a premium connection between Number Theory and Graph Theory. On behalf of modular arithmetic, we can manipulate many fascinating features of graphs. We first encounter the ideas used in [1–5], where digraphs from congruences were discussed. The conditions for regularity and semiregularity of such digraphs are presented in [1, 2]. The necessary and sufficient conditions for the existence of isolated fixed points have been established in [3]. The structures of symmetric digraphs have been studied in [4, 5]. In this paper we discuss the graph G(n) arriving from exponential congruences. We assign to each pair of positive integers a and b an edge (a,b) of the graph G(n) if the congruence ax≡b(modn) is solvable, where V={0,1,…,n-1} is the set of vertices of G(n) and E⊆V×V is the set of edges of G(n). Then the graph G(n) has a loop at a vertex a if and only if ax≡a(modn) admits a solution. Since the congruence relation is an equivalence relation, so ax≡a(modn), a∈{0,1,…,n-1} always admits a solution x=1. Thus we call x=1 a trivial solution and, so far, the loops due to trivial solution are called trivial loops. Thus it becomes interesting to find the number of vertices in {0,1,…,n-1} such that the congruence ax≡a(modn) admits a nontrivial solution. The loops at vertices corresponding to nontrivial solutions are called nontrivial loops. Since for each α≥2, the congruence aα≡a(modn), for a=0,1, so the loops at vertices 0 and 1 will be considered as nontrivial loops. We denote the number L(n) for nontrivial loops of the graph G(n). Let n=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes. The number L(n) of the graph G(n) has been determined and shown to be equal to ∏i=1r‍(ϕ(piki)+1), where ϕ is the Euler’s phi function. It has been shown that the graph G(n) has 2r components. We label these components as Γd, where d∣n or d=ϕ(n). The order of each component of the graph G(n) has been determined. Further, it is proved that the component Γp of the simple graph G(p2) is always a tree with root at zero. Also if n is a Fermat’s prime, then the component Γϕ(n) of the simple graph G(n) is a complete graph.


## 2. Preliminaries

A graphG is simple if it is free from loops and multiedges. The vertices a1,a2,…,ak-1,ak will constitute a cycle of length k if each of the following congruences is solvable:
(2.1)a1x≡a2(modn),a2x≡a3(modn),⋮akx≡a1(modn).
A graph G is said to be connected if there is a path from x to y, for each pair of vertices x and y. A maximal connected subgraph is called a component [6].In Figure1, the simple graph G(30) has eight components. A graph G is complete if every two distinct vertices of G are adjacent. Thus G(n) is complete if ax≡b(modn) is solvable for each distinct pair of vertices in V. The degree of a vertex v in G is the number of edges incident with v. It is denoted by deg(v). If deg(v)=r for each vertex v of G(n), then G(n) is called r-regular or regular graph of degree r. The simple graph G(30) has two 3-regular and two 1-regular components.Figure 1
The simple graph ofG(30).We recall the definition of Euler’s phi function [7], and some of its properties.Definition 2.1.
Forn≥1, let ϕ(n) denote the number of positive integers not exceeding n which are relatively prime to n. Note that ϕ(1)=1, because gcd(1,1)=1. Thus we can write
(2.2)ϕ(n)={1,ifn=1,Numberofintegerslessthannandco-primeton,ifn≠1.
By the definition of Euler’s phi function, it is clear that if a∣b, then ϕ(a)∣ϕ(b). Also ϕ(p)=p-1 if and only if p is a prime number. We will need the following results of [7], regarding Euler’s phi function, for use in the sequel.Theorem 2.2.
Ifp is a prime and k>0, then
(2.3)ϕ(pk)=pk-1(p-1).
Let f be an arithmetic function. One recalls that f is said to be multiplicative if f(mn)=f(m)f(n), gcd(m,n)=1.The following theorem is the generalization of the well-known Fermat’s Little theorem which states that if(a,p)=1, then ap≡1(modp).Theorem 2.3 (Euler).
Ifn≥1 and (a,n)=1, then aϕ(n)≡1(modn).Definition 2.4 (see [7]).
A set ofk integers is a complete residue system (CRS) modulo k if every integer is congruent to exactly one of the modulo k. If we delete integers from CRS, which are not prime to k, then the remaining integers will constitute the reduced residue system (RRS) modulo k.Theorem 2.5 (counting principle [8]).
If a work is distributed overr1,r2,…,rt, objects with r1 object occuring s1 ways, r2 object occuring s2 ways, and rt object occuring st ways, then the work can be done in s1s2⋯st ways.Theorem 2.6 (the inclusion-exclusion principle [9]).
LetA1,A2,…,An be n finite sets. Then
(2.4)|⋃i=1nAi|=∑1≤i≤n‍|Ai|-∑1≤i<j≤n‍|Ai∩Aj|+∑1≤i<j<k≤n‍|Ai∩Aj∩Ak|-⋯+(-1)n+1|⋂i=1nAi|.


## 3. Applications of Euler’s Phi Function

In Graph Theory, a loop or a self-loop is an edge that connects a vertex to itself. A vertex of an undirected graph is called an isolated vertex if it is not the endpoint of any edge. This means that it is not connected with any other vertex of the graph. Thus in our case, the vertexv is an isolated vertex if and only if vx≡u(modn), v≠u is not solvable. Now if we omit the condition of simplicity in our graph, then this isolated vertex will contribute twice in the degree as there will be a self-loop at v as the congruence vx≡v(modn) is solvable. This leads to the following results.Theorem 3.1.
Letn=2p1p2⋯pk be the prime factorization of n, where p1<p2<⋯<pk are distinct, odd primes. Then 0 and p1p2⋯pk are isolated vertices of G(n). That is, the vertices 0 and p1p2⋯pk are not the endpoints of any edge in graph G(n) except loop at these vertices.Proof.
The elementa, where 0≤a≤n-1, is an isolated point of the graph G(n) if and only if the solvability of ax≡b(modn) implies that a=b. It is trivial that 0 is an isolated point of G(n) as ax≡0(mod2p1p2⋯pk) is solvable if and only if a≡0(mod2p1p2⋯pk). Moreover, p1<p2<⋯<pk are distinct, odd primes, so for some integer β>1, (p1p2⋯pk)β-1-1 is an even integer. Thus 2p1p2⋯pk∣p1p2⋯pk((p1p2⋯pk)β-1-1) and hence (p1p2⋯pk)x≡p1p2⋯pk(mod2p1p2⋯pk) is solvable with root β. Next, we claim that the congruence (p1p2⋯pk)x≡a(mod2p1p2⋯pk), a≢p1p2⋯pk(mod2p1p2⋯pk) is not solvable. To prove our assertion, let a≢p1p2⋯pk(mod2p1p2⋯pk) and suppose there exists an integer α≥1, such that the congruence, (p1p2⋯pk)α≡a(mod2p1p2⋯pk) is balanced. Then there exists some integer t such that
(3.1)(p1p2⋯pk)α=a+2p1p2⋯pkt.
This implies that p1p2⋯pk((p1p2⋯pk)α-1-2t)=a. But then p1p2⋯pk∣a. Let a=t1p1p2⋯pk for some integer t1. If t1 is even, then 2p1p2⋯pk∣a and hence by (3.1), 2p1p2⋯pk∣(p1p2⋯pk)α, a contradiction as (p1p2⋯pk)α is an odd integer. So let t1=2r+1, for some integer r. Then a=t1p1p2⋯pk=(2r+1)p1p2⋯pk and this shows that 2p1p2⋯pk∣a-p1p2⋯pk which is a contradiction against the fact that a≢p1p2⋯pk(mod2p1p2⋯pk). Finally, the congruence (p1p2⋯pk)x≡0(mod2p1p2⋯pk) is not solvable since an odd integer is not divisible by an even integer. Hence 0 and p1p2⋯pk are not adjacent as well.Corollary 3.2.
Ifn is an odd square free integer, then 0 is the only isolated vertex of the graph G(n).Theorem 3.3.
Letn=p1k1p2k2⋯prkr be the prime power factorization of a non-square-free integer n, where p1<p2<⋯<pk are distinct primes, ki≥1 and r≥1. Then 0 and kp, where k=0,1,…,⌊n/p⌋, and p=p1p2⋯pk, are always adjacent vertices in G(n).Proof.
We show that the congruence(kp)x≡0(modn) is solvable for all k=0,1,…,⌊n/p⌋. Let p, q be two distinct primes such that n=pq2. Then (kpq)2=k2p2q2=k2p(pq2)≡0(modn). Thus x=2 is the solution of the congruence (kpq)x≡0(modpq2). We follow the fashion explained above. For this, take n=p1k1p2k2⋯prkr. Let t=lcm(p1,p2,…,pk), then there exist integers t1,t2,…,tk such that t=tiki, for each i=1,2,…,k. Let m=∏i=1r‍piki(ti-1). Then it is easy to see that
(3.2)(kp)t=ktp1t1k1p2t2k2⋯prtrkr=ktmn≡0(modn).
This shows that x=t=lcm(p1,p2,…,pk) is the solution of the congruence, (kp)x≡0(modn). Hence, kp and 0 are the adjacent vertices in G(n).The following results give a formula for finding the number of nontrivial self-loops of the graphG(n).Lemma 3.4.
Letp be a prime number. Let n=pk, k≥2 and let ϕ be the Euler’s phi function. Then L(n)=ϕ(pk)+1.Proof.
Letn=pk, k≥2. A vertex v of the graph G(n) has a self-loop if and only if vx≡v  (mod n) is solvable. Thus to find the number of self-loops in G(n), we need to count the number of vertices v in CRS(modn) such that the congruence vx≡v(modn) is solvable. By Euler’s Theorem, if (a,n)=1, then ax≡1(modn) is solvable with x=ϕ(n) as its root, whence ax≡a(modn) is solvable with x=ϕ(n)+1. Since p,2p,…,pk-1·p are the pk-1 integers which are not prime to pk, so there are pk-pk-1=ϕ(pk) integers in CRS(modn) for which the congruence ax≡a(modn) is solvable. Also, for each k≥1, the vertex 0 has self-loop in G(pk). Thus there are ϕ(pk)+1 self-loops. For the case, if a∈{p,2p,…,pk-1·p}, with α as the solution of ax≡a(modpk). Then aα-1≡1(modpk-1) implies that aα-1≡1(modp). This yields a contradiction against the fact that if a∈{p,2p,…,pk-1·p}, then aα-1≡0(modp). Hence, there exist no vertex a∈{p,2p,…,pk-1·p}, for which ax≡a(modn) is solvable. Thus ϕ(pk)+1 are the only vertices for which the graph G(n) has self-loops.The following theorem provides us the cardinality of the set of those vertices ofG(n) which have nontrivial self-loops, where n=p1k1p2k2⋯prkr and r≥2.Theorem 3.5.
Letn=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes, ki≥1 and r≥2. Then
(3.3)L(n)=∏i=1r(ϕ(piki)+1).Proof.
We apply induction onr. By Lemma 3.4, result is true for r=1. Suppose result is true for r-1 distinct prime factors. That is, if m=p1k1p2k2⋯pr-1kr-1, then L(m)=∏i=1r-1‍(ϕ(piki)+1). Let n=p1k1p2k2⋯prkr=mprkr. Now, the congruence ax≡a(modmprkr) is solvable if and only if the congruences ax≡a(modm) and ax≡a(modprkr) are solvable. But by induction, the graph G(m) has ∏i=1r-1‍(ϕ(piki)+1) self-loops and, by Lemma 3.4, the graph G(prkr) has ϕ(prkr)+1 self-loops. Hence, by Theorem 2.5, the graph G(n) has ∏i=1r‍(ϕ(piki)+1) self-loops. This through our result. In Figure 2, we depict Theorem 3.5 for n=24.Figure 2
The graphG(24) has 15 nontrivial self-loops.Corollary 3.6.
Letn=p1p2⋯pr be the prime factorization of a square-free integer n, where p1<p2<⋯<pk are distinct primes and r≥2. Then
(3.4)L(n)=p1p2⋯pr.Proof.
It is easy to see thatϕ(p)+1=p, for any prime p. Thus by Theorem 3.5, corollary follows. That is,
(3.5)L(n)=p1p2⋯pr.Corollary 3.7.
Letm and n be two non-square-free integers such that gcd(m,n)=1. Then,
(3.6)L(mn)=L(m)L(n).


## 4. Components and Their Characteristics

Recall that a maximal connected subgraph of a graphG is called a component. For instance, the vertices v1,v2,…,vr from CRS (modn) will constitute a component of the graph G(n) if for each i,1≤i≤r, there exist some j,1≤j≤r such that vix≡vj(modn) is solvable, for all i≠j. The following theorem explores some interesting characteristics of components for the simple graph G(n).Theorem 4.1 (main theorem).
Letn=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes, ki≥1 and r≥1. Then,(a)
G(n) has 2r components,(b)
ifn=p2, p is a prime number, then Γp is a tree with root at 0,(c)
ifn is a Fermat’s prime, then Γϕ(n) is complete. Let n=p1k1p2k2⋯prkr. Then p1,p2,…,pr,p1p2,…,p1pr,…,p1p2⋯pr are the possible square-free positive divisors of n. We see that the sets of vertices generated by these divisors will constitute components of G(n). We label these components by Γp1,Γp2,…,Γpr,Γp1p2,…,Γp1p2⋯pr. Moreover, the set of all those residues of n which are prime to n will provide us another component. Since this set contains ϕ(n) vertices from V={0,1,2,…,n-1}, so, for the sake of convenience, we label this component by Γϕ(n). Before giving the proof of Theorem 4.1, we prove the following results.Lemma 4.2.
(a) Letn=pk,k>0, where p is a prime number. Then G(n) has 2 components, namely, Γϕ(n) and Γp.
(b) Letn=p1k1p2k2⋯prkr and k=Πi=1spi, 1≤s≤r. Then the order of the component Γk is
(4.1)|V(Γk)|=⌊nk⌋-∑s<j≤r‍⌊nkpj⌋+∑s<j<k≤r‍⌊nkpjpk⌋+⋯+(-1)r-s⌊nkps+1ps+2⋯pr⌋.Proof.
(
a
) Recall that an integer a such that (a,pk)=1 is called a primitive root modulo pk only if a is of order pk-1(p-1). Let r be a primitive root of pk. Then the smallest integer k is called the index of a with respect to r if rk≡a(modpk). Moreover, it is well known that the exponential congruence ax≡b(modpk) is solvable if and only if d∣indrb, where d=(indra,pk-1(p-1)). We divide the numbers 0,1,2,…,(p-1)pk into two sets, one of which is {0,p,2p,…,(p-1)pk-1} and the other is RRS modulo pk. We claim that these two sets constitute independent components of G(pk). Let V={r1,r2,…,rϕ(pk)} where each ri,1≤i≤ϕ(pk) is prime to pk, the set of vertices of the component Γϕ(pk). Then every vertex of Γϕ(pk) must have some index with respect to primitive root r. Thus the exponential congruence ax≡1(modpk) is solvable since indr1=0 and is divisible by d, where, d=(indra,pk-1(p-1)). This means that each vertex of the set Γϕ(pk) is adjacent with 1. So it must contribute as one component of the graph G(pk). Moreover, for any integer m≥0, pk∣(mp)k and hence (mp)x≡0(modpk) is solvable with x=k as its root. Thus each vertices of the set {0,p,2p,…,(p-1)pk-1} is adjacent with 0. Then V(Γp)={0,p,2p,…,(p-1)pk-1} will form another component of the graph G(pk). Next we claim that none of the vertex Γϕ(pk) is adjacent with any of the vertex Γp. To prove our assertion, let u and v be two vertices of G(pk) such that u∈Γϕ(pk) and v∈Γp. Then there exist integers r and s such that
(4.2)ur≡1(modpk),vs≡0(modpk).
Let t=lcm(r,s), then there exist integers r1 and s1 such that t=rr1=ss1. Hence by (4.2), we get
(4.3)ut≡1(modpk),vt≡0(modpk).
Now, if u and v are adjacent, then there must be some integer α such that uα≡v(modpk). Then by (4.3), we obtain, 0≡1(modpk) which is absurd. This is through the claim. Hence Γϕ(n) and Γp are the only components of G(pk). The part (b) is the direct consequence of Theorem 2.6.Corollary 4.3.
Fork=1,V(Γp)={0}.Two graphs or two components of a graph are said to be isomorphic to each other if there is an isomorphism between their vertex sets. Thus, ifG(n) and G(m) are isomorphic, then |V(G(n))|=|V(G(m))|. Moreover if the vertices u and v are adjacent in G(n), then f(u) and f(v) must be adjacent in G(m), where f is an isomorphism between their sets of vertices. The following corollary can easily be proved by using Lemma 4.2 and Corollary 3.7.Corollary 4.4.
Ifn=2p1p2⋯pr and l, m are prime divisors of n, then Γl and Γm, are nonisomorphic components of G(n).Proof.
Since bothl and m are prime numbers, so by Lemma 4.2 (b), the order of components Γl and Γm must be different. Hence both can never be isomorphic. For instance, take n=30, l=3, and m=5. Then by Lemma 4.2 (b),
(4.4)|V(Γ3)|=⌊303⌋-(⌊303.2⌋+⌊303.5⌋)+⌊303.2.5⌋=4,|V(Γ5)|=⌊305⌋-(⌊305.2⌋+⌊305.3⌋)+⌊305.2.3⌋=2.
Hence by (4.4), the components Γ3 and Γ5 are not isomorphic in G(30). However, |V(Γ3)|=|V(Γ6)|=4. Thus the isomorphism can be established between the components Γ3 and Γ6 in G(30) if they possess the same structure as well. This leads to the following corollary.Corollary 4.5.
Letn=2p1p2⋯pr and d∣n. If Γd and Γ2d are the components of G(n), then Γd≅Γ2d.Proof of Main Theorem.
(a) It is well known thatax≡b(modp1k1p2k2⋯prkr) is solvable if and only if the congruence ax≡b(modpiki) is solvable for each i=1,2,…,r. Then the proof is analogous to Theorem 2.5 together with Lemma 4.2.
(b) It is easy to see that each element ofV(Γp)={0,p,…,(p-1)p} in G(p2) is connected with 0 since for each α≥2, (tp)α≡0(modp2), 1≤t≤p-1 is satisfied. This shows that the congruence ax≡0(modp2) is solvable for each a∈V(Γp) in G(p2). To show that Γp in G(p2) is a tree, we claim that the nonzero vertices in V(Γp) are not connected to each other. To prove our assertion, let (t1p)α≡t2p(modp2) for α≥2 and 1≤t1<t2≤p-1. Then by Cancelation Law of congruences, we obtain, t1αpα-1≡t2(modp). As p∣t1αpα-1-t2 and p∣t1αpα-1, so by the simple divisibility rules, p∣t2. But t2≤p-1<p, thus we arrive at a contradiction. This through our claim and finally the component Γp in G(p2) is a tree with root at zero.
(c) It is wellknown thatFn, n>4 is always composite. Thus the only Fermat’s primes are 3, 5, 17, 257, and 65537. Let us write n=2k+1, k=1,2,4,8,16. Then ϕ(n)=2k, k=1,2,4,8,16 since n is prime. To show that the component Γϕ(n) is complete, we need to show that the congruence ax≡b(modn) is solvable for each a,b∈{1,2,…,n-1}. By [9], every odd prime p has a primitive root. Since Fermat’s numbers are always odd, so each of the Fermat’s prime has a primitive root. Let it be r. Then the congruence ax≡b(modn) is solvable if and only if the congruence xindra≡indrb(mod2k) is solvable, where k=1,2,4,8,16. As indra, indrb∈{1,2,…,n-1}, so the later congruence reduced to the linear congruence αx≡β(mod2k), where α=indra and β=indrb. Then the simple graph G(n) will be complete if the congruence αx≡β(mod2k), or the congruence βx≡α(mod2k), is solvable. To prove our assertion, it is easy to see that either (α,2k)=1=(β,2k) or (α,2k)=2t=(β,2k), where 1≤t≤2k. For the first case, the congruence αx≡β(mod2k), is solvable and has a unique solution. To discuss the rest of the case, we let (α,2k)=2t1 and (β,2k)=2t2, 1≤t1, t2≤2k. If t1≤t2, then (α,2k)∣(β,2k), so the linear congruence αx≡β(mod2k) is solvable and has 2t1 solutions. But if t2<t1, we replace α and β and solve the congruence βx≡α(mod2k), which is solvable and has 2t2 solutions. Thus in either case, we see that there is an edge (α,β), α, β∈{1,2,…,n-1} in component Γϕ(n) of the simple graph G(n) when n is a Fermat’s prime.The following corollaries are the direct consequences of Theorem4.1.Corollary 4.6.
Letn=t2, where t is square free integer. Then Γt is a tree with root at zero.Corollary 4.7.
Ifn is Fermat prime, then Γϕ(n) is regular of degree ϕ(n)-1.


## 5. Conclusions

This piece of work describes the relationship of exponential congruences with graphs. It has been explored that an exponential congruence yields a set of graphs. Also certain components of the graphs form trees if self-loops are suppressed. The types of graphs and trees were hence yielded form a pattern based on the nature of variables within the congruence. The major results formed show that the componentΓϕ(n) of the simple graph G(n) is complete if n is Fermat’s prime and also that the component Γt2, where t is a square free integer, is always a tree. Intuitively, the results formed find their place in various applications of number theory, encryption, and algorithms. In various problems of data decryption using brute force method it is desirable to find the nature of a number and establish if it is divisible by some other prime number or not. Such problems can be tackled by forming a graph of its exponential congruence and determine the pattern formed by its components. Moreover these exponential congruences can be established as a succinct representation of graphs of a specific nature for their applications in various computer algorithms.



---

*Source: 292895-2012-10-03.xml*