On a problem of D. H. Lehmer

Abstract:

Let $p$ be an odd prime number. For $n\in \{1,\ldots ,p-1\}$ we denote the inverse of $n$ modulo $p$ by $n^{*}$ with $n^{*}\in \{1,\ldots ,p-1\}$. Given $\varepsilon >0$, we prove that in any range $n\in \{N+1,\ldots ,N+L\}\subseteq \{1,\ldots ,p-1\}$ of length $L\geq p^{1/2+\varepsilon }$ the probability that $n^{*}$ has the same parity as $n$ tends to $1/2$ as $p\rightarrow +\infty$. This result was previously known only to hold true in the full range $n\in \{1,\ldots ,p-1\}$ of length $L=p-1$. We will also obtain quantitative results on the pseudorandomness of the sequence $(-1)^{n+n^{*}}$ for which we estimate the well-distribution $W$ and correlation measures $C_k$ as defined by Mauduit and Sárközy (1997).