\documentclass[12pt]{article}
\textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt
\evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt
\parskip=10pt
\font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9

\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsxtra}

\newcommand{\Dst}[1]{{\displaystyle #1}}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{conj}{Conjecture}

\def\B{\hfill $\Box$}

\begin{document}

\begin{center}
{\bf DISTRIBUTION OF DIFFERENCE BETWEEN INVERSES OF
CONSECUTIVE INTEGERS MODULO $P$}
%{\bf Distribution of Differences between Inverses of Consecutive
%Integers Modulo $p$} 
\vskip 20pt
{\bf Tsz Ho Chan}\\
{\smallit Department of Mathematics, Case Western Reserve University,
Cleveland, OH 44106, USA}\\
{\tt txc50@cwru.edu} 
\end{center}
\vskip 30pt \centerline{\smallit Received: 11/19/03, Revised:
2/9/04, Accepted:
3/24/04, Published: 3/25/04} \vskip 30pt

\centerline{\bf Abstract} Let $p>2$ be a prime number. For each
integer $0< n < p$, define $\overline{n}$ by the congruence
$n\overline{n} \equiv 1 \pmod{p}$ with $0 < \overline{n} < p$. We
are led to study the distribution behavior of $\overline{n} -
\overline{n+1}$ in order to prove the asymptotic formula
$$\sum_{n=1}^{p-2} |\overline{n} - \overline{n+1}| = \frac{1}{3}p^2 +
O(p^{3/2} \log^3{p}).$$

\noindent

\pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4
(2004), \#A03\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 30pt

%-----------------------------------------------------------------
\section*{\normalsize 1. Introduction}
For any prime $p$ and any integer $0 < n < p$, there is one and
only one $\overline{n}$ with $0 < \overline{n} < p$ satisfying $n
\overline{n} \equiv 1 \pmod{p}$. We are interested in how the
inverses $\overline{n}$ fluctuate as $n$ runs from $1$ to $p-1$.
In particular, we look at the sum
\begin{equation}
\label{sum} S_p = \sum_{n=1}^{p-2} |\overline{n} - \overline{n+1}|
\end{equation}
For any integer $k$, one can easily show that there are at most
$2$ solutions to the congruence equation $\overline{n} -
\overline{n+1} \equiv k \pmod{p}$. From this, we have
$$\frac{1}{8}p^2 - \frac{1}{2}p \leq \sum_{n=1}^{[p/4]} 4k \leq
S_p \leq \sum_{n=p-[p/4]-2}^{p-2} 4k \leq \frac{7}{8}p^2 +
\frac{7}{2}p$$ where $[x]$ denotes the greatest integer $\leq x$.
So, $S_p$ has order $p^2$ and the natural question is whether
$\lim_{p \rightarrow \infty} S_p / p^2$ exists. To this, we have
the following.
\begin{thm}
\label{theorem1} For any prime $p>2$, $$S_p = \sum_{n=1}^{p-2}
|\overline{n} - \overline{n+1}| = \frac{1}{3}p^2 + O(p^{3/2}
\log^3{p}).$$
\end{thm}
Hence, on average, the difference between inverses of consecutive
integers, $|\overline{n} - \overline{n+1}|$, is about $p/3$. More
generally, we have the following result.
\begin{thm}
\label{theorem2} For any prime $p>2$ and $\lambda > 0$,
$$\sum_{n=1}^{p-2} |\overline{n} - \overline{n+1}|^\lambda =
\frac{2}{(\lambda+1)(\lambda+2)}p^{\lambda+1} + O(p^{\lambda+1/2}
\log^3{p}).$$
\end{thm}

To prove Theorem \ref{theorem1} or \ref{theorem2}, we are led to
study
\begin{equation*}
\begin{split} 
& T_{+}(p,k) = \# \{n : 0 < n < p, 0 < \overline{n} -
\overline{n+1} \leq k\}, \\  
& T_{-}(p,k) = \# \{n : 0 < n < p, -k \leq \overline{n} -
\overline{n+1} < 0\}, \mbox{ and }  \\ 
& T(p,k) = T_{+}(p,k) + T_{-}(p,k) = \# \{n : 0 < n <
p, 0 < |\overline{n} - \overline{n+1}| \leq k \}
\end{split}
\end{equation*}
for integer $0 < k < p$. We have
\begin{thm}
\label{theorem3} For any prime $p>2$ and any integer $0 < k < p$,
$$T_{\pm}(p,k) = k - \frac{k^2}{2p} + O(p^{1/2} \log^3{p}).$$
\end{thm}
Our method of proof is motivated by Professor W.P. Zhang's paper
[\ref{Z}] involving Kloosterman sums and trigonometric sums. The
proofs of Theorems \ref{theorem1}, \ref{theorem2} and
\ref{theorem3} extend to pairs $\overline{n}$ and $\overline{n+l}$
for fixed integer $l \not\equiv 0 \pmod{p}$ with slight
modifications.
%------------------------------------------------------------------
\vskip 30pt

\section*{\normalsize 2. Exponential and Kloosterman sums}
First, we start with some notation. Letting $e(y) = e^{2\pi i y}$,
we denote the
Kloosterman sum
$$S(m,n;q) := \mathop{\sum_{d\pmod{q}}}_{(d,q)=1} e\Bigl(\frac{m
d + n \overline{d}}{q}\Bigr).$$
\begin{lem}
\label{lemma1.5} Let $p$ be a prime number. For any integer $a$
and $b \not\equiv 0 \pmod{p}$,
$$\mathop{\sum\nolimits'}_{x=1}^{p} e\Bigl(\frac{\frac{ax+b}{x(x
\pm 1)}}{p}\Bigr) \ll p^{1/2}$$ where $\sum'$ is over all $x
\pmod{p}$ except the roots of $x(x \pm 1)$ in $F_p$.
\end{lem}

\noindent
{\it Proof.} It follows from the Bombieri-Weil bound [\ref{B}] for
exponential sums in the form by Moreno and Moreno [\ref{MM},
Theorem $2$] provided that $\frac{ax+b}{x(x \pm 1)}$ is not of the
form $h(x)^p - h(x)$ with $h(x) \in \overline{F}_p$, where
$\overline{F}_p$ is the algebraic closure of $F_p$. This is true
in our situation. For otherwise, say
$$\frac{ax+b}{x(x \pm 1)} = \Bigl(\frac{F(x)}{G(x)}\Bigr)^p -
\frac{F(x)}{G(x)}$$ with $F(x)$ and $G(x)$ polynomials over
$\overline{F}_p$ such that $(F(x),G(x))=1$. Then
\begin{equation}
\label{1.5.1} (ax + b) G(x)^p = x(x \pm 1) F(x) (F(x)^{p-1} -
G(x)^{p-1}).
\end{equation}
Since $F(x)$ and $G(x)$ are relatively prime, we have $G(x)^p |
x(x \pm 1)$. This forces $G(x)$ to be a nonzero constant
polynomial. Contradiction occurs if one compares the degrees in
(\ref{1.5.1}).
\B
%--------------------------------
\begin{lem}
\label{lemma2} Let $p>2$ be a prime number. For any integers $r$
and $s$,
\begin{equation}
\label{2.1} \sum_{n=1}^{p-1} e\Bigl(\frac{\pm n}{p}\Bigr) S(r,n;p)
\overline{S(s,n;p)} \ll p^{3/2}.
\end{equation}
Here $\overline{S(s,n;p)}$ stands for the complex conjugate of
$S(s,n;p)$.
\end{lem}

\noindent
{\it Proof.}
\begin{enumerate}
\item $r \equiv 0 \pmod{p}$. Then $S(r,n;p) = -1$ for $1 \leq n
\leq p-1$. So, the left side of (\ref{2.1}) is
\begin{equation*}
\begin{split}
=& \sum_{n=1}^{p-1} e\Bigl(\frac{\pm n}{p}\Bigr) \sum_{d=1}^{p-1}
e\Bigl(\frac{-sd-n\overline{d}}{p}\Bigr) \\
=& \sum_{d=1}^{p-1} e\Bigl(\frac{-s d}{p}\Bigr) \sum_{n=1}^{p-1}
e\Bigl(\frac{-n(\overline{d} \mp 1)}{p}\Bigr) \ll
\mathop{\sum_{d=1}^{p-1}}_{\overline{d} \not\equiv \pm 1 (p)} 1 +
p \ll p.
\end{split}
\end{equation*}
%
\item $s \equiv 0 \pmod{p}$. Similar to case 1.
%
\item $r \not\equiv s \pmod{p}$ and $(r,p)=1=(s,p)$. The left hand
side of (\ref{2.1})
\begin{equation*}
\begin{split}
=& \sum_{n=1}^{p-1} e\Bigl(\frac{\pm n}{p}\Bigr) \sum_{a=1}^{p-1}
e\Bigl(\frac{ra + n\overline{a}}{p}\Bigr) \sum_{b=1}^{p-1}
e\Bigl(\frac{-sb - n\overline{b}}{p}\Bigr) \\
=& \sum_{a=1}^{p-1} \sum_{b=1}^{p-1} e\Bigl(\frac{ra -
sb}{p}\Bigr) \sum_{n=1}^{p-1} e\Bigl(\frac{(\overline{a} -
\overline{b} \pm 1) n}{p}\Bigr) \\
=& \sum_{c=1}^{p-1} \sum_{d=1}^{p-1} e\Bigl(\frac{r\overline{c} -
s\overline{d}}{p}\Bigr) \sum_{n=1}^{p-1} e\Bigl(\frac{(c-d \pm 1)
n}{p}\Bigr) \\
=& (p-1) \mathop{\sum\nolimits'}_{d=1}^{p} e\Bigl(\frac{r
\overline{d \mp 1} - s \overline{d}}{p}\Bigr) -
\mathop{\sum_{c=1}^{p-1} \sum_{d=1}^{p-1}}_{c \neq d \mp 1}
e\Bigl(\frac{r\overline{c} - s \overline{d}}{p}\Bigr) \\
=& p \mathop{\sum\nolimits'}_{d=1}^{p} e\Bigl(\frac{r \overline{d
\mp 1} - s \overline{d}}{p}\Bigr) - \sum_{c=1}^{p-1}
e\Bigl(\frac{r \overline{c}}{p}\Bigr) \sum_{d=1}^{p-1}
e\Bigl(\frac{-s \overline{d}}{p}\Bigr) \\
=& p \mathop{\sum\nolimits'}_{d=1}^{p} e\Bigl(\frac{[(r-s)d \pm s]
\overline{d (d \mp 1)}}{p}\Bigr) - 1 \ll p \sqrt{p}
\end{split}
\end{equation*}
by Lemma \ref{lemma1.5}. Here $\sum'$ means summation over all $d$
with $(d,p) = 1 =(d \mp 1,p)$. Note: The first sum in the second
last line is a special case of Cobeli and Zaharescu [\ref{CZ},
Lemma $1$] or Cobeli, Gonek and Zaharescu [\ref{CGZ}, Lemma $1$].
%
\item $r \equiv s \not\equiv 0 \pmod{p}$. Similar to case 3.
\B
\end{enumerate}

%----------------------------------------------------------------
\vskip 30pt

\section*{\normalsize 3. Theorem \ref{theorem3} when $ 0 < k < p/2$}
Now, we try to express $T_{\pm}(p,k)$ as exponential sums similar
to [\ref{Z}].

\begin{lem}
\label{lemma3} For any prime $p > 2$ and any integer $0 < k <
p/2$,
\begin{equation*}
\begin{split}
T_{\pm}(p,k) =& \frac{1}{p^2} \sum_{m=1}^{p} \sum_{n=1}^{p}
e\Bigl(\frac{-n}{p}\Bigr) \sum_{t=1}^{k} e\Bigl(\frac{\mp m
t}{p}\Bigr) \biggl[\sum_{a=1}^{p-1} \sum_{b=1}^{p-k}
e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp
mb \pm n\overline{b}}{p}\Bigr) \\
&+ \sum_{a=p-k+1}^{p-1} \sum_{b=p-k+1}^{p-1} e\Bigl(\frac{\pm ma
\mp n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp mb \pm
n\overline{b}}{p}\Bigr) \biggr].
\end{split}
\end{equation*}
\end{lem}

\noindent
{\it Proof.} We shall only prove the formula for $T_{+}(p,k)$; the
proof for
$T_{-}(p,k)$ is  similar. Observe that $T_{+}(p,k) = \# \{a: 0
< a - b \leq k, \overline{b} - \overline{a} = 1\}$. Thus, as
\begin{equation}
\label{orthogonal} \sum_{n=1}^{p} e\Bigl(\frac{nr}{p}\Bigr) =
\left\{ \begin{array}{ll} p, & p\; | r; \\
0, & p \not| r,
\end{array} \right.
\end{equation}
\begin{equation}
\label{1}
\begin{split}
T_{+}(p,k) =& \sum_{t=1}^{k} \mathop{\sum_{a=1}^{p-1}
\sum_{b=1}^{p-1}}_{a-b = t, \overline{b} - \overline{a} = 1} 1
\\
=& \frac{1}{p^2} \sum_{m=1}^{p} \sum_{n=1}^{p} \sum_{t=1}^{k}
\mathop{\sum_{a=1}^{p-1} \sum_{b=1}^{p-1}}_{a > b}
e\Bigl(\frac{m(a-b-t)}{p}\Bigr) e\Bigl(\frac{n(\overline{b} -
\overline{a} -1)}{p}\Bigr) \\
=& \frac{1}{p^2} \sum_{m=1}^{p} \sum_{n=1}^{p}
e\Bigl(\frac{-n}{p}\Bigr) \sum_{t=1}^{k} e\Bigl(\frac{-m
t}{p}\Bigr) \biggl[\mathop{\sum_{a=1}^{p-1} \sum_{b=1}^{p-k}}_{a >
b} e\Bigl(\frac{ma-n\overline{a}}{p}\Bigr) e\Bigl(\frac{-mb + n
\overline{b}}{p}\Bigr) \\
&+ \mathop{\sum_{a=p-k+1}^{p-1} \sum_{b=p-k+1}^{p-1}}_{a > b}
e\Bigl(\frac{ma-n\overline{a}}{p}\Bigr) e\Bigl(\frac{-mb + n
\overline{b}}{p}\Bigr) \biggr]
\end{split}
\end{equation}
Note that we do not need the condition $\overline{b} >
\overline{a}$ because $-p+2 \leq \overline{b} - \overline{a} \leq
p-2$ which does not allow $\overline{b} - \overline{a} = 1 - p$
(the only alternative besides $1$ may be counted). Now $t-p \leq
k-p$. It is valid to drop the condition $a > b$ in both double
sums within the brackets because $k-p < 1-(p-k) \leq a - b$ and
$k-p < -k < (p-k+1) - (p-1) \leq a-b$ respectively (note: $k<p/2$
is used for the second chain of inequalities). Hence, only $a-b=t$
is counted even without condition $a>b$ and we have the lemma.
\B

\begin{lem}
\label{lemma4} For any prime $p>2$ and any integer $0 < k < p$,
\begin{equation*}
\begin{split}
& \sum_{m=1}^{p} \sum_{n=1}^{p} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp m t}{p}\Bigr) \sum_{a=1}^{p-1}
\sum_{b=1}^{p-k} e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr)
e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& kp(p-k) + O(p^{5/2} \log^2{p}).
\end{split}
\end{equation*}
\end{lem}

\noindent
{\it Proof.} We separate the left hand side into three pieces
according to: (i) $m=n=p$, (ii) $n=p$ and $1 \leq m \leq p-1$,
(iii) $1 \leq m \leq p$ and $1 \leq n \leq p-1$. The left hand
side of Lemma \ref{lemma4}
\begin{equation}
\label{4.0}
\begin{split}
=& kp(p-k) + O(p^2) + \sum_{m=1}^{p-1} \sum_{t=1}^{k}
e\Bigl(\frac{\mp mt}{p}\Bigr) \sum_{a=1}^{p-1} \sum_{b=1}^{p-k}
e\Bigl(\frac{\pm ma}{p}\Bigr) e\Bigl(\frac{\mp mb}{p}\Bigr) \\
+& \sum_{m=1}^{p} \sum_{n=1}^{p-1} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp mt}{p}\Bigr) \sum_{a=1}^{p-1}
\sum_{b=1}^{p-k} e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr)
e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& kp(p-k) + O(p^2) + S_1 + S_2.
\end{split}
\end{equation}
\begin{equation}
\label{4.1} S_1 \leq \sum_{m=1}^{p-1} \Big|\sum_{t=1}^{k}
e\Bigl(\frac{\mp mt}{p}\Bigr) \Big| \Big|\sum_{b=1}^{p-k}
e\Bigl(\frac{\mp mb}{p}\Bigr) \Big| \leq \sum_{m=1}^{p-1}
\frac{1}{|\sin{(\pi m/p)}|^2} \ll \sum_{m=1}^{p-1} \frac{p^2}{m^2}
\ll p^2
\end{equation}
by summing the geometric series and $\sin{\pi x} \geq 2x$ for $0
\leq x \leq 1/2$. By (\ref{orthogonal}),
\begin{equation*}
\begin{split}
& \sum_{a=1}^{p-1} \sum_{b=1}^{p-k} e\Bigl(\frac{\pm ma \mp
n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}
\Bigr) \\
=& \frac{1}{p} \sum_{r=1}^{p} \sum_{a=1}^{p-1} \sum_{b=1}^{p-1}
e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp
mb \pm n\overline{b}}{p}\Bigr) \sum_{c=1}^{p-k}
e\Bigl(\frac{r(b-c)}{p}\Bigr) \\
=& \frac{1}{p} \sum_{r=1}^{p}  \sum_{c=1}^{p-k}
e\Bigl(\frac{-cr}{p}\Bigr) S(r \mp m,\pm n;p) \overline{S(\mp
m,\pm n;p)}.
\end{split}
\end{equation*}
Hence, by Lemma \ref{lemma2},
\begin{equation}
\label{4.2}
\begin{split} S_2 \ll& \frac{1}{p} \sum_{m=1}^{p} \Big|\sum_{t=1}^{k}
e\Bigl(\frac{\mp mt}{p}\Bigr) \Big| \sum_{r=1}^{p-1} \Big|
\sum_{c=1}^{p-k} e\Bigl(\frac{-cr}{p}\Bigr) \Big| p^{3/2} +
\sum_{m=1}^{p} \Big|\sum_{t=1}^{k} e\Bigl(\frac{\mp mt}{p}\Bigr)
\Big| p^{3/2} \\
\ll& p^{1/2} k \sum_{r=1}^{p-1} \frac{1}{|\sin{(\pi r/p)}|} +
p^{1/2}\Bigl[\sum_{m=1}^{p-1} \frac{1}{|\sin{(\pi m/p)}|}\Bigr]^2
+ p^{3/2} k \\
+& p^{3/2} \sum_{m=1}^{p-1} \frac{1}{|\sin{(\pi m/p)}|} \ll
p^{1/2} \Bigl[\sum_{m=1}^{[p/2]} \frac{p}{m}\Bigr]^2 + p^{3/2}
\sum_{m=1}^{[p/2]} \frac{p}{m} \ll p^{5/2} \log^2{p}.
\end{split}
\end{equation}
Combining (\ref{4.0}), (\ref{4.1}) and (\ref{4.2}), we have the
lemma.
\B
%--------------------------------------------
\begin{lem}
\label{lemma5} For any prime $p>2$ and any integer $0 < k < p/2$,
\begin{equation*}
\begin{split}
& \sum_{m=1}^{p} \sum_{n=1}^{p} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp m t}{p}\Bigr) \sum_{a=p-k+1}^{p-1}
\sum_{b=p-k+1}^{p-1} e\Bigl(\frac{\pm ma \mp n\overline{a}}
{p}\Bigr) e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& \frac{1}{2}p k^2 + O(p^{5/2} \log^3{p}).
\end{split}
\end{equation*}
\end{lem}

\noindent
{\it Proof.} Similar to Lemma \ref{lemma4}, we split the left hand
side into three pieces which
\begin{equation}
\label{5.0}
\begin{split}
=& k^3 + O(p^2) + \sum_{m=1}^{p-1} \sum_{t=1}^{k} e\Bigl(\frac{\mp
m t}{p}\Bigr) \sum_{a=p-k+1}^{p-1} \sum_{b=p-k+1}^{p-1}
e\Bigl(\frac{\pm ma}{p}\Bigr) e\Bigl(\frac{\mp mb}{p}\Bigr) \\
&+ \sum_{m=1}^{p} \sum_{n=1}^{p-1} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp mt}{p}\Bigr) \sum_{a=p-k+1}^{p-1}
\sum_{b=p-k+1}^{p-1} e\Bigl(\frac{\pm ma \mp n\overline{a}}
{p}\Bigr) e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& k^3 + O(p^2) + S_1 + S_2.
\end{split}
\end{equation}
Replacing $a$ by $p-a$ and $b$ by $p-b$,
\begin{equation}
\label{5.1}
\begin{split}
S_1 =& \sum_{m=1}^{p-1} \sum_{t=1}^{k} e\Bigl(\frac{\mp m
t}{p}\Bigr) \sum_{a=1}^{k-1} \sum_{b=1}^{k-1}
e\Bigl(\frac{\mp ma}{p}\Bigr) e\Bigl(\frac{\pm mb}{p}\Bigr) \\
=& \sum_{t=1}^{k} \sum_{a=1}^{k-1} \sum_{b=1}^{k-1} \sum_{m=1}^{p}
e\Bigl(\frac{\pm m(b-a-t)}{p}\Bigr) - k^3 + O(k^2) \\
=& p \sum_{t=1}^{k} \mathop{\sum_{a=1}^{k-1} \sum_{b=1}^{k-1}}_{b
- a = t} 1 - k^3 + O(k^2) = \frac{1}{2} p k^2 - k^3 + O(pk)
\end{split}
\end{equation}
because we may count $b-a=t$ or $b-a=t-p$ but the second case is
not possible as $t-p \leq k-p < -k+2 \leq b-a$. Here $k < p/2$ is
crucial.

Applying (\ref{orthogonal}) twice,
\begin{equation*}
\begin{split}
& \sum_{a=p-k+1}^{p-1} \sum_{b=p-k+1}^{p-1} e\Bigl(\frac{\pm ma
\mp n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp mb \pm n
\overline{b}}{p}\Bigr) \\
=& \frac{1}{p^2} \sum_{r=1}^{p} \sum_{s=1}^{p} \sum_{a=1}^{p-1}
\sum_{b=1}^{p-1} e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr)
e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
&\times \sum_{c=p-k+1}^{p-1} e\Bigl(\frac{r(a-c)}{p}\Bigr)
\sum_{d=p-k+1}^{p-1} e\Bigl(\frac{s(b-d)}{p}\Bigr) \\
=& \frac{1}{p^2} \sum_{r=1}^{p} \sum_{s=1}^{p} K(r) K(s) S(s \mp
m,\pm n;p) \overline{S(\mp m-r,\pm n;p)}
\end{split}
\end{equation*}
where $K(x) = \sum_{n=p-k+1}^{p-1} e(-nx/p)$. Rearranging the sums
and applying Lemma \ref{lemma2},
\begin{equation}
\label{5.2}
\begin{split}
S_2 =& \frac{1}{p^2} \sum_{m=1}^{p} \sum_{t=1}^{k} e\Bigl(\frac{m
t}{p}\Bigr) \sum_{r=1}^{p} \sum_{s=1}^{p} K(r) K(s) \\
&\times \sum_{n=1}^{p-1} e\Bigl(\frac{-n}{p}\Bigr) S(s \mp m,\pm
n;p) \overline{S(\mp m-r,\pm n;p)} \\
\ll& \frac{1}{p^{1/2}} \sum_{m=1}^{p} \Big|\sum_{t=1}^{k}
e\Bigl(\frac{m t}{p}\Bigr)\Big| \sum_{r=1}^{p} |K(r)|
\sum_{s=1}^{p} |K(s)| \\
\ll& \frac{1}{p^{1/2}} \Bigl[k + \sum_{m=1}^{[p/2]}
\frac{1}{|\sin{(\pi m/p)}|}\Bigr]^3 \ll \frac{1}{p^{1/2}} (k +
p\log{p})^3 \ll p^{5/2} \log^3{p}.
\end{split}
\end{equation}
Combining (\ref{5.0}), (\ref{5.1}) and (\ref{5.2}), we have the
lemma.
\B
%-------------------------------------------

\newpage
To prove  Theorem \ref{theorem3} when $0 < k < p/2$, apply Lemma
\ref{lemma4} and \ref{lemma5} to Lemma \ref{lemma3} and get
\begin{equation*}
T_{\pm}(p,k) = \frac{1}{p^2} \Bigl[kp(p-k) + \frac{1}{2}pk^2 +
O(p^{5/2} \log^3{p})\Bigr] = k - \frac{k^2}{2p} + O(p^{1/2}
\log^3{p})
\end{equation*}
which gives Theorem \ref{theorem3} in that range of $k$.
%-----------------------------------------------------------------
\vskip 30pt

\section*{\normalsize 4. Theorem \ref{theorem3} when $p/2 < k < p$}
Before proceeding, let us introduce some notation.
\begin{equation*}
\begin{split}
U_{+}(p,k) =& \# \{n : 0 < n < p, p-k \leq \overline{n} -
\overline{n+1} < p\}, \\
U_{-}(p,k) =& \# \{n : 0 < n < p, -p < \overline{n} -
\overline{n+1} \leq -p + k \}, \\
V_{+}(p,k) =& \# \{n ; 0 < n < p, \overline{n} - \overline{n+1}
\equiv t \pmod{p} \mbox{ for } 1 \leq t \leq k \}, \\
V_{-}(p,k) =& \# \{n ; 0 < n < p, \overline{n} - \overline{n+1}
\equiv -t \pmod{p} \mbox{ for } 1 \leq t \leq k \}.
\end{split}
\end{equation*}
Then one can easily see that
\begin{equation}
\label{more} V_{+}(p,k) = T_{+}(p,k) + U_{-}(p,k) \mbox{ and }
V_{-}(p,k) = T_{-}(p,k) + U_{+}(p,k).
\end{equation}

\begin{lem}
\label{lemma6} For any prime $p>2$ and any integer $0 < k < p$,
$$V_{\pm}(p,k) = \frac{1}{p^2} \sum_{m=1}^{p} \sum_{n=1}^{p}
e\Bigl(\frac{-n}{p}\Bigr) \sum_{t=1}^{k} e\Bigl(\frac{\mp m
t}{p}\Bigr) \sum_{a=1}^{p-1} \sum_{b=1}^{p-1} e\Bigl(\frac{\pm ma
\mp n\overline{a}}{p}\Bigr) e\Bigl(\frac{\mp mb \pm
n\overline{b}}{p}\Bigr).$$
\end{lem}

\noindent
{\it Proof.} Use (\ref{orthogonal}). Note: it is easier than Lemma
\ref{lemma3} because one does not need to worry about $a > b$ or
$a < b$.
\B

\begin{lem}
\label{lemma7} For any prime $p>2$ and any integer $0 < k < p$,
\begin{equation*}
\begin{split}
& \sum_{m=1}^{p} \sum_{n=1}^{p} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp m t}{p}\Bigr) \sum_{a=1}^{p-1}
\sum_{b=1}^{p-1} e\Bigl(\frac{\pm ma \mp n\overline{a}}{p}\Bigr)
e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& k p^2 + O(p^{5/2} \log{p})
\end{split}
\end{equation*}
\end{lem}

\noindent
{\it Proof.} Similar to Lemma \ref{lemma4}, we split the left hand
side into three pieces which
\begin{equation}
\label{7.0}
\begin{split}
=& k p^2 + O(p^2) + \sum_{m=1}^{p-1} \sum_{t=1}^{k}
e\Bigl(\frac{\mp m t}{p}\Bigr) \sum_{a=1}^{p-1} \sum_{b=1}^{p-1}
e\Bigl(\frac{\pm ma}{p}\Bigr) e\Bigl(\frac{\mp mb}{p}\Bigr) \\
&+ \sum_{m=1}^{p} \sum_{n=1}^{p-1} e\Bigl(\frac{-n}{p}\Bigr)
\sum_{t=1}^{k} e\Bigl(\frac{\mp mt}{p}\Bigr) \sum_{a=1}^{p-1}
\sum_{b=1}^{p-1} e\Bigl(\frac{\pm ma \mp n\overline{a}}
{p}\Bigr) e\Bigl(\frac{\mp mb \pm n\overline{b}}{p}\Bigr) \\
=& k p^2 + O(p^2) + S_1 + S_2.
\end{split}
\end{equation}
By (\ref{orthogonal}),
\begin{equation}
\label{7.1} S_1 \leq \sum_{m=1}^{p-1} \sum_{t=1}^{k} 1 \ll p^2.
\end{equation}
After rearranging summations,
\begin{equation}
\label{7.2}
\begin{split}
S_2 =& \sum_{m=1}^{p} \sum_{t=1}^{k} e\Bigl(\frac{\mp mt}{p}\Bigr)
\sum_{n=1}^{p-1} e\Bigl(\frac{-n}{p}\Bigr) S(\mp m, \pm n; p)
\overline{S(\mp m, \pm n; p)} \\
\ll& p^{3/2} \sum_{m=1}^{p} \Bigl|\sum_{t=1}^{k} e\Bigl(\frac{\mp
mt}{p}\Bigr)\Bigr| \\
\ll& p^{3/2} \Bigl[k + \sum_{m=1}^{[p/2]} \frac{1}{|\sin{(\pi
m/p)}|} \Bigr] \ll p^{3/2} (k + p\log{p}) \ll p^{5/2} \log{p}
\end{split}
\end{equation}
by Lemma \ref{lemma2}, summing the geometric series and $\sin{(\pi
x)} \geq 2x$. We have the lemma by (\ref{7.0}), (\ref{7.1}) and
(\ref{7.2}).
\B

\begin{lem}
\label{lemma8} For any prime $p>2$ and any integer $0 \leq k <
p/2$,
$$U_{\pm}(p,k) = \frac{k^2}{2p} + O(p^{1/2} \log^3{p}).$$
\end{lem}

\noindent
{\it Proof.} First note that when $k = 0$, $U_{\pm}(p,k) = 0$. Now
assume $k > 0$. From (\ref{more}), $U_{\pm}(p,k) = V_{\mp}(p,k) -
T_{\mp}(p,k)$. Thus, by Lemma \ref{lemma6}, \ref{lemma7} and
Theorem \ref{theorem3} in the range $0 < k < p/2$,
$$U_{\pm}(p,k) = k + O(p^{1/2} \log{p}) - \Bigl(k - \frac{k^2}{2p}
+ O(p^{1/2} \log^3{p})\Bigr)$$ which gives the lemma.
\B

To prove Theorem \ref{theorem3} when $p/2 < k < p$, observe that
$0 \leq p-k-1 < p/2$ and
\begin{equation*}
\begin{split}
T_{\pm}(p,k) =& T_{\pm}\Bigl(p, \frac{p-1}{2}\Bigr) + \Bigl[
U_{\pm}\Bigl(p, \frac{p-1}{2}\Bigr) - U_{\pm}(p, p-k-1) \Bigr] \\
=& \frac{p-1}{2} - \frac{(\frac{p-1}{2})^2}{2p} + \Bigl[
\frac{(\frac{p-1}{2})^2}{2p} - \frac{(p-k-1)^2}{2p} \Bigr]
+ O(p^{1/2} \log^3{p}) \\
=& \frac{p}{2} - \frac{p^2 - 2pk + k^2}{2p} + O(1) + O(p^{1/2} \log^3{p}) \\
=& k - \frac{k^2}{2p} + O(p^{1/2} \log^3{p})
\end{split}
\end{equation*}
by Theorem \ref{theorem3} in the range $0 < k < p/2$ and Lemma
\ref{lemma8}.
%-----------------------------------------------------------------
\vskip 30pt

\section*{\normalsize 5. Proof of Theorems \ref{theorem1} and
\ref{theorem2}} By Theorem \ref{theorem3}, $T(p,k) = 2k - k^2/p + O(p^{1/2}
\log^3{p})$ for integer $0 < k < p$. More generally,
\begin{equation}
\label{final} T(p,u) = \# \{n : 0 < |\overline{n} -
\overline{n+1}| \leq u\} = 2u - \frac{u^2}{p} +
O(p^{1/2}\log^3{p})
\end{equation}
for any real number $0 \leq u \leq p$. Using the Riemann-Stieltjes
integral, integration by parts, and (\ref{final}),
\begin{equation*}
\begin{split}
& \sum_{n=1}^{p-2} |\overline{n} - \overline{n+1}|^\lambda =
\int_{0}^{p} u^\lambda\, d T(p,u) = T(p,p) p^\lambda - \lambda
\int_{0}^{p} u^{\lambda - 1} T(p,u) du
\\
=& p^{\lambda+1} + O(p^{\lambda}) - \lambda \int_{0}^{p}
2u^\lambda - \frac{u^{\lambda+1}}{p} + O(u^{\lambda-1} p^{1/2}
\log^3{p})\, du \\
=& p^{\lambda+1} - \Bigl[\frac{2\lambda}{\lambda+1} p^{\lambda+1}
- \frac{\lambda}{\lambda+2} p^{\lambda+1} \Bigr] +
O(p^{\lambda+1/2}\log^3{p}) \\
=& \frac{2}{(\lambda+1)(\lambda+2)} p^{\lambda+1} +
O(p^{\lambda+1/2}\log^3{p})
\end{split}
\end{equation*}
which gives Theorem \ref{theorem2} and hence Theorem
\ref{theorem1}.

Numerical calculations (by a C++ program) suggest that the error
term in Theorem \ref{theorem3} is probably best possible except
for the extra logarithms.

Let $m_{p}^{\pm} = \max_{1 \leq k < p} |T_{\pm}(p,k) - (k -
\frac{k^2}{2p})|$.

\begin{math}
\begin{array}{c|c|c|c|c|c|c|c|c}
p & 101 & 103 & 107 & 109 & 113 & 127 & 131 & 137 \\
\hline m_p^+ / \sqrt{p} & 0.4951 & 0.6103 & 0.9794 & 0.7504 &
0.4595 & 0.9122 & 0.6133 & 0.6401 \\
\hline m_p^- / \sqrt{p} & 0.5951 & 0.7098 & 0.6993 & 0.4956 &
0.4812 & 0.7976 & 0.9067 & 0.5416
\end{array}
\end{math}

\begin{math}
\begin{array}{c|c|c|c|c|c|c|c|c}
p & 5501 & 5503 & 5507 & 5519 & 5521 & 5527 & 5531 & 5557 \\
\hline m_p^+ / \sqrt{p} & 0.5786 & 0.6384 & 0.7021 & 0.6350 &
1.1337 & 0.4528 & 0.6928 & 0.7150 \\
\hline m_p^- / \sqrt{p} & 0.5945 & 0.6532 & 0.7342 & 0.5888 &
1.0775 & 0.4621 & 0.7291 & 0.7530
\end{array}
\end{math}

\begin{math}
\begin{array}{c|c|c|c|c|c|c|c|c}
p & 12301 & 12323 & 12329 & 12343 & 12347 & 12373 & 12377 & 12379 \\
\hline m_p^+ / \sqrt{p} & 0.5249 & 0.6978 & 0.8166 & 1.0416 &
1.1251 & 0.6540 & 0.8172 & 0.6914 \\
\hline m_p^- / \sqrt{p} & 0.5521 & 0.6745 & 0.8101 & 1.0346 &
1.1069 & 0.6789 & 0.8144 & 0.6778
\end{array}
\end{math}

\begin{math}
\begin{array}{c|c|c|c|c|c|c|c|c}
p & 60013 & 60017 & 60029 & 60037 & 60041 & 60077 & 60083 & 60089 \\
\hline m_p^+ / \sqrt{p} & 0.5172 & 0.7776& 0.5806 & 0.8265 &
0.8441 & 0.9457 & 0.4469 & 0.5922 \\
\hline m_p^- / \sqrt{p} & 0.5312 & 0.7789 & 0.5792 & 0.8411 &
0.8489 & 0.9514 & 0.4373 & 0.5897
\end{array}
\end{math}

\newpage
We conclude with the following
\begin{conj}
$$m_p^{\pm} \ll p^{1/2} \; \mbox{ and } \; m_p^+ - m_p^- =
o(p^{1/2}).$$
\end{conj}

\noindent
{\bf Note:} After finishing this paper, we came across Cobeli and
Zaharescu [\ref{CZ}], and found that it is far more general and
would give
$$T_{\pm}(p,k) = k - \frac{k^2}{2p} + O(p^{5/6}\log^{2/3}{p}).$$
Hence their method gives our results except for a bigger error
term.

%--------------------------------------------------------------
\begin{thebibliography}{9}
%--------------------------------------------------------------
\item\label{B} E. Bombieri, {\em On exponential sums in finite
fields}, Amer. J. Math. {\bf 88} (1966), 71-105.
%--------------------------------------------------------------
\item\label{CZ} C.I. Cobeli and A. Zaharescu, {\em The order of
inverses mod $q$}, Mathematika {\bf 47} (2000), 87-108.
%--------------------------------------------------------------
\item\label{CGZ} C.I. Cobeli, S.M. Gonek and A. Zaharescu, {\em
The distribution of patterns of inverses modulo a prime}, J.
Number Theory {\bf 101} (2003), 209-222.
%--------------------------------------------------------------
\item\label{MM}  C.J. Moreno and O. Moreno, {\em Exponential sums
and Goppa codes. I},  Proc. Amer. Math. Soc. {\bf 111} (1991), no.
2, 523-531.
%--------------------------------------------------------------
\item\label{Z} W.P. Zhang, {\em On the Distribution of Inverses
Modulo $n$}, J. Number Theory {\bf 61} (1996), 301-310.
\end{thebibliography}

\end{document}