# The Maximal Difference of Different Powers of an Element Modulon

Authors: Jinyun Qi; Zhefeng Xu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we investigate the maximal difference of integer powers of an element modulon. Let an denote the integer b with 1≤b≤n such that a≡bmodn for any integer a. Using the bounds for exponential sums, we obtain a lower bound of the function Hm1,m2n:=maxam1n−am2n:1≤a≤n,a,n=1, which gives n−Hm1,m2n=On3/4+o1.


---

## Body

## 1. Introduction

Letn≥3 be an integer and 1≤a≤n be an integer with a,n=1. We know that there exists a unique integer c such that ac≡1modn, where c is called the inverse of a modulo n with 1≤c<n. We denote c by a¯. The difference between an element and its inverse modulo n has been studied by several mathematicians.Zhang [1] is the first person to explicitly study the distribution between an integer and its inverse modulo n, proving that(1)∑′a=1na−a¯2k=ϕnn2k2k+1k+1+O4kn4k+1/2d2nln2n,where ϕn is the Euler function and dn is the divisor function.Zhang [2] gives some further results for the distribution of a−a¯. For any 0<δ≤1, he defines that(2)Sn,δ=#a:0≤a≤1,a,n=1,a−a¯<δn,where ♯△ denotes the number of the elements in △ and shows that(3)Sn,δ=δ2−δϕn+On1/2d2nln3n.Meanwhile, Zheng [3] obtains similar results in a more general context. More generalizations of [1, 2] are in recent papers [4–7].Our object in this paper is to study the maximal difference of different powers of an element modulon. The investigation for the maximal difference of different powers of a modulo n is motivated by the problem of the maximal difference of a−a¯, where a and a¯ run through the set 0,1,…,n−1 such that aa¯≡1modn. Khan [8] defines(4)Mn=maxa−a¯:1≤a≤n,a,n=1,proving that(5)Mn≤n−2n−1.Later, Khan and Shaparlinski [9] show that(6)n−Mn=on3/4+o1.Letn≥3 be an integer and ℤn denote residues’ modulo n. In this paper, we assume these residues to consist of the elements 0,1,2,…,n−1. We write ℤn∗ to be the set of elements relatively prime to ℤn. Let an be the integer b with 1≤b≤n such that a≡bmodn for any integer a. Define(7)Hm1,m2n:=maxam1n−am2n:1≤a≤n,a∈ℤn∗.We prove the following theorems.Theorem 1.
Letn≥3be an integer. Then, for arbitrary given positive integersm1,m2, we have(8)n−Hm1,m2n=On3/4+o1.In fact, we obtain a more general result which gives a lower bound forHm1,m2:Theorem 2.
Letn≥3be an integer. Then, for arbitrary given positive integersm1,m2, we have(9)Hm1,m2n≥n−4tωnn3/2dn+tωnn3/2dn2+ζ3/2n1/2+o1σ2nϕn1/2ϕn+2,where t=maxm1,m2.By applying Theorem2, one can obtain the following.Corollary 1.
Letn≥3be an integer. Then, for arbitrary given positive integersm1,m2, we have(10)n−Hm1,m2n≤4ζ1/232+o1n9/4+o1ϕ−3/2n.


## 2. Preliminaries

### 2.1. Notations

In this paper,t is the integer part of t. We denote the group of units of ℤn by ℤn∗; thus, the cardinality of ℤn∗ is given by the Euler function ϕn. Let ωn be the counting function of the number of distinct primes. The number and the sum of the divisor function are defined by(11)dn=∑k∣n1,σn=∑k∣n,k>0k=n∑k∣n,k>01k,and the Riemann zeta function is written by(12)ζs=∑z=1∞1zs.In what follows, we use the Landau symbolO with the understanding that any implied constants are absolute. For given functions F and G, the notation F=OG is equivalent to the statement that the inequality F≤cG holds with some constant c≥0.We recall the identity which follows from the formula of the sum of a geometric progression:(13)∑r=0n−1erwn=n,w≡0modn0,w≡0modn,where ez=e2πiz.


### 2.2. Several Lemmas

We need several lemmas to prove our theorems.Lemma 1.
For anyd∣n, withd≤n, there holds(14)∑r∈ℤnr,n=d∑x=0h−1erxn2≤nhd.Proof.
(see Lemma 17.3 in [10]).Lemma 2.
Letpbe a prime andube an integer withu,p=1. Then, for any integersk≥2andα≥2, there holds(15)∑a=1pαp∤aeuakpα≤kpα/2.Proof.
This can be easily obtained from formula (0.5) in [11].Lemma 3.
Letn>1be an integer andkbe a fixed positive integer. For any integeruwithu,n=1, we have the following estimation:(16)∑a∈ℤn∗euakn≤kωnn1/2.Proof.
Letn=p1α1p2α2,…,prαr be the prime factor decomposition of n. Note that(17)∑a∈ℤn∗euakn=∏i=1r∑a∈ℤpiαi∗eun/piαik−1akpiαi.
In fact, ifm and l pass through a reduced residue system modulo n1 and n2, respectively, mn2+ln1 passes through a reduced system modulo n1n2. One can write(18)∑a∈ℤn∗euakn=∑m∈ℤn1∗∑l∈ℤn2∗eumn2+ln1kn1n2=∑m∈ℤn1∗eumn2kn1n2∑l∈ℤn2∗euln1kn1n2=∑m∈ℤn1∗eun2k−1mkn1∑l∈ℤn2∗eun1k−1lkn2.
This yields identity (17). By Lemma 2, we get Lemma 3.Lemma 4.
Letm1,m2be fixed integers. Then, the bound,(19)maxu1,u2,n=g∑a∈ℤn∗eu1am1+u2am2n≤g1/2n1/2+o1,holds.Proof.
It is easily obtained from Lemma 1 in [12].To introduce the following lemma better, we define(20)Sd,f=∑r,s∈ℤnr+s>0r,n=ds,n=f∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.Lemma 5.
For anydnandfn, we have(21)Sd,f≤m1ωnn3/2h3d−1/2,f=n;m2ωnn3/2h3f−1/2,d=n;n5/2h2d,f1/2df,d<n,f<n.Proof.
We begin with the case whenf=n. Apparently, this indicates that s=0 and r≠0. From Lemma 1 and 3, we derive(22)Sd,n=h2∑r∈ℤnr,n=d∑x∈ℤn∗erxm1n∑x=0h−1erxn2=h2∑r∈ℤnr,n=dd∑x∈ℤn/d∗er/dxm1n/d∑x=0h−1erxn2≤n3/2h3m1ωnd−1/2.
Using a similar method, we have the estimation,(23)Sn,f≤n3/2h3m2ωnf−1/2.
We now consider the cased<nandf<n. By Lemma 1 and 4, one obtains(24)Sd,f≤n1/2+o1∑r∈ℤnr,n=d∑s∈ℤns,n=fr,s,n1/2∑x=0h−1erxn2∑x=0h−1esxn2≤n1/2+o1d,f,n1/2n2h2df≤n5/2+o1h2d,f1/2df.
This completes the proof.


### 2.3. Proofs of the Theorems

Now, we complete the proofs of our main results.Proof.
of Theorem2. We denote by V the number of the solution of congruences:(25)xm1≡h−y+zmodn,xm2≡−h+u−vmodn.
In the following, we show the range ofh in the case that congruences (25) are solvable for x∈ℤn∗, and integers 0≤y,z,u,v≤h−1. Then, it can be easily deduced that(26)Hm1,m2n≥n−4h+2.
Applying the exponential sums identity (13), we have(27)V=∑x∈ℤn∗∑y,z,u,v=0h−11n2∑r,s∈ℤnerxm1−h+y−z+sxm2+h−u+vn=1n2∑r,s∈ℤne−rh+shn∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.
Provided thatr=0ands=0, the right-hand side of equation (27) is ϕnh4/n2. Then, we have(28)V−ϕnh4n2≤1n2∑r,s∈ℤnr+s>0∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.
From Lemma5, one can write(29)V−ϕnh4n2≤1n2∑r+s>0∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2=1n2∑d|n,d<nSd,n+∑f∣n,f<nSn,f+∑dn,fnd,f<nSd,f≤1n2m1ωn+m2ωnn3/2h3dn+n5/2+o1h2∑d∣n,f∣nd,f1/2df.
We know(30)∑d|n,f|nd,f1/2df≤∑k|nk1/2∑d|n/k∑f|n/k1k2df=∑k∣nk−3/2∑d|n/k∑f|n/k1df≤ζ32σnn2.
Remark thatt=maxm1,m2, so we can get the inequality(31)n2V−ϕnh4≤m1ωn+m2ωnn3/2h3dn+ζ32σ2nn1/2+o1h2≤2tωnn3/2h3dn+ζ32σ2nn1/2+o1h2.
After a simple calculation, one can write(32)n2V≥h2ϕnh2−2tωnn3/2hdn−ζ32σ2nn1/2+o1.
The right-hand side of (32) has to be positive. It suffices to show that(33)ϕnh2−2tωnn3/2hdn−ζ32σ2nn1/2+o1≥0.
Multiplying both side of inequality (33) by ϕn and calculating briefly, we have(34)ϕnh−n3/2dntωn2≥n3/2dntωn2+ζ32σ2nn1/2+o1.
Hence,(35)h≥tωnn3/2dn+tωnn3/2dn2+ζ32n1/2+o1σ2nϕn1/2ϕ−1n.
This finishes the proof of Theorem2.Proof.
of Corollary1. Applying Theorem 2, one can obtain(36)n−Hm1,m2n≤4tωnn3/2dn+tωnn3/2dn2+ζ32n1/2+o1σ2nϕn1/2ϕ−1n≤42tωnn3/2dn+ζ1/232n1/4+o1σnϕ1/2nϕ−1n≤8tωnn3/2dnϕ−1n+4ζ1/232n9/4+o1ϕ−3/2n≤4ζ1/232+o1n9/4+o1ϕ−3/2n,where we use the bounds(37)σnϕn≤n2,ωn=Olognloglogn,logdn=Olognloglogn.
The proof of Corollary1 is complete.Proof.
of Theorem1. Combining Corollary 1 with the bounds,(38)nϕn=Ologlogn.
See Theorem 328 in [10]; Theorem 1 follows immediately.


## 2.1. Notations

In this paper,t is the integer part of t. We denote the group of units of ℤn by ℤn∗; thus, the cardinality of ℤn∗ is given by the Euler function ϕn. Let ωn be the counting function of the number of distinct primes. The number and the sum of the divisor function are defined by(11)dn=∑k∣n1,σn=∑k∣n,k>0k=n∑k∣n,k>01k,and the Riemann zeta function is written by(12)ζs=∑z=1∞1zs.In what follows, we use the Landau symbolO with the understanding that any implied constants are absolute. For given functions F and G, the notation F=OG is equivalent to the statement that the inequality F≤cG holds with some constant c≥0.We recall the identity which follows from the formula of the sum of a geometric progression:(13)∑r=0n−1erwn=n,w≡0modn0,w≡0modn,where ez=e2πiz.


## 2.2. Several Lemmas

We need several lemmas to prove our theorems.Lemma 1.
For anyd∣n, withd≤n, there holds(14)∑r∈ℤnr,n=d∑x=0h−1erxn2≤nhd.Proof.
(see Lemma 17.3 in [10]).Lemma 2.
Letpbe a prime andube an integer withu,p=1. Then, for any integersk≥2andα≥2, there holds(15)∑a=1pαp∤aeuakpα≤kpα/2.Proof.
This can be easily obtained from formula (0.5) in [11].Lemma 3.
Letn>1be an integer andkbe a fixed positive integer. For any integeruwithu,n=1, we have the following estimation:(16)∑a∈ℤn∗euakn≤kωnn1/2.Proof.
Letn=p1α1p2α2,…,prαr be the prime factor decomposition of n. Note that(17)∑a∈ℤn∗euakn=∏i=1r∑a∈ℤpiαi∗eun/piαik−1akpiαi.
In fact, ifm and l pass through a reduced residue system modulo n1 and n2, respectively, mn2+ln1 passes through a reduced system modulo n1n2. One can write(18)∑a∈ℤn∗euakn=∑m∈ℤn1∗∑l∈ℤn2∗eumn2+ln1kn1n2=∑m∈ℤn1∗eumn2kn1n2∑l∈ℤn2∗euln1kn1n2=∑m∈ℤn1∗eun2k−1mkn1∑l∈ℤn2∗eun1k−1lkn2.
This yields identity (17). By Lemma 2, we get Lemma 3.Lemma 4.
Letm1,m2be fixed integers. Then, the bound,(19)maxu1,u2,n=g∑a∈ℤn∗eu1am1+u2am2n≤g1/2n1/2+o1,holds.Proof.
It is easily obtained from Lemma 1 in [12].To introduce the following lemma better, we define(20)Sd,f=∑r,s∈ℤnr+s>0r,n=ds,n=f∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.Lemma 5.
For anydnandfn, we have(21)Sd,f≤m1ωnn3/2h3d−1/2,f=n;m2ωnn3/2h3f−1/2,d=n;n5/2h2d,f1/2df,d<n,f<n.Proof.
We begin with the case whenf=n. Apparently, this indicates that s=0 and r≠0. From Lemma 1 and 3, we derive(22)Sd,n=h2∑r∈ℤnr,n=d∑x∈ℤn∗erxm1n∑x=0h−1erxn2=h2∑r∈ℤnr,n=dd∑x∈ℤn/d∗er/dxm1n/d∑x=0h−1erxn2≤n3/2h3m1ωnd−1/2.
Using a similar method, we have the estimation,(23)Sn,f≤n3/2h3m2ωnf−1/2.
We now consider the cased<nandf<n. By Lemma 1 and 4, one obtains(24)Sd,f≤n1/2+o1∑r∈ℤnr,n=d∑s∈ℤns,n=fr,s,n1/2∑x=0h−1erxn2∑x=0h−1esxn2≤n1/2+o1d,f,n1/2n2h2df≤n5/2+o1h2d,f1/2df.
This completes the proof.


## 2.3. Proofs of the Theorems

Now, we complete the proofs of our main results.Proof.
of Theorem2. We denote by V the number of the solution of congruences:(25)xm1≡h−y+zmodn,xm2≡−h+u−vmodn.
In the following, we show the range ofh in the case that congruences (25) are solvable for x∈ℤn∗, and integers 0≤y,z,u,v≤h−1. Then, it can be easily deduced that(26)Hm1,m2n≥n−4h+2.
Applying the exponential sums identity (13), we have(27)V=∑x∈ℤn∗∑y,z,u,v=0h−11n2∑r,s∈ℤnerxm1−h+y−z+sxm2+h−u+vn=1n2∑r,s∈ℤne−rh+shn∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.
Provided thatr=0ands=0, the right-hand side of equation (27) is ϕnh4/n2. Then, we have(28)V−ϕnh4n2≤1n2∑r,s∈ℤnr+s>0∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2.
From Lemma5, one can write(29)V−ϕnh4n2≤1n2∑r+s>0∑x∈ℤn∗erxm1+sxm2n∑x=0h−1erxn2∑x=0h−1esxn2=1n2∑d|n,d<nSd,n+∑f∣n,f<nSn,f+∑dn,fnd,f<nSd,f≤1n2m1ωn+m2ωnn3/2h3dn+n5/2+o1h2∑d∣n,f∣nd,f1/2df.
We know(30)∑d|n,f|nd,f1/2df≤∑k|nk1/2∑d|n/k∑f|n/k1k2df=∑k∣nk−3/2∑d|n/k∑f|n/k1df≤ζ32σnn2.
Remark thatt=maxm1,m2, so we can get the inequality(31)n2V−ϕnh4≤m1ωn+m2ωnn3/2h3dn+ζ32σ2nn1/2+o1h2≤2tωnn3/2h3dn+ζ32σ2nn1/2+o1h2.
After a simple calculation, one can write(32)n2V≥h2ϕnh2−2tωnn3/2hdn−ζ32σ2nn1/2+o1.
The right-hand side of (32) has to be positive. It suffices to show that(33)ϕnh2−2tωnn3/2hdn−ζ32σ2nn1/2+o1≥0.
Multiplying both side of inequality (33) by ϕn and calculating briefly, we have(34)ϕnh−n3/2dntωn2≥n3/2dntωn2+ζ32σ2nn1/2+o1.
Hence,(35)h≥tωnn3/2dn+tωnn3/2dn2+ζ32n1/2+o1σ2nϕn1/2ϕ−1n.
This finishes the proof of Theorem2.Proof.
of Corollary1. Applying Theorem 2, one can obtain(36)n−Hm1,m2n≤4tωnn3/2dn+tωnn3/2dn2+ζ32n1/2+o1σ2nϕn1/2ϕ−1n≤42tωnn3/2dn+ζ1/232n1/4+o1σnϕ1/2nϕ−1n≤8tωnn3/2dnϕ−1n+4ζ1/232n9/4+o1ϕ−3/2n≤4ζ1/232+o1n9/4+o1ϕ−3/2n,where we use the bounds(37)σnϕn≤n2,ωn=Olognloglogn,logdn=Olognloglogn.
The proof of Corollary1 is complete.Proof.
of Theorem1. Combining Corollary 1 with the bounds,(38)nϕn=Ologlogn.
See Theorem 328 in [10]; Theorem 1 follows immediately.



---

*Source: 8002211-2021-12-27.xml*