# Small residue classes with small reciprocal

Let $p$ be a large prime. For any $m \in \{1,\ldots,p-1\}$, let $\overline{m} \in \{1,\ldots,p-1\}$ be the reciprocal in ${\bf Z}/p{\bf Z}$ (i.e. the unique element of $\{1,\ldots,p-1\}$ such that $m \overline{m} = 1 \hbox{ mod } p$).

I am interested in finding $m$ for which for which $m$ and $\overline{m}$ are both small compared with $p$, excluding the trivial case $m=1$ of course. For instance, using Weil's bound on Kloosterman sums and some Fourier analysis, it is not difficult to show that there exists nontrivial $m$ with $\max(m, \overline{m}) \ll p^{3/4}$. But this does not look sharp; probabilistic heuristics suggest that one should be able to get $\max(m, \overline{m})$ as small as $O(p^{1/2})$ or so (ignoring log factors), which would clearly be best possible. Is some improvement on the $O(p^{3/4})$ bound known? For my specific application I would like to reach $O(p^{2/3})$. (I would also be willing to do some averaging in $p$ if this improves the bounds. I'm actually more interested in asymptotics for the number of $m$ with $\max(m,\overline{m})$ bounded by a given threshold, but the existence problem already looks nontrivial.)

I tried playing around with Karatsuba's bounds for incomplete Kloosterman sums, but it was not clear to me how to use them to get both $m$ and $\overline{m}$ into intervals smaller than $p^{3/4}$.

-
In a paper available at nieuwarchief.nl/serie5/deel01/dec2000/pdf/heathbrown.pdf Heath-Brown discusses this exact problem (in the section entitled "an elementary problem") and obtains $p^{3/4}$. He indicates that it is an open problem to improve on $3/4$. I haven't thought about how averaging over $p$ could improve the exponent but often that can be very helpful. – Matt Young Jul 5 '11 at 2:05
Ah, thanks! A bit disappointed that it is open (at least as of 2000), but I guess I wasn't missing an utterly trivial argument at least. That paper mentions an improved Kloosterman sum estimate of Kuznetsov that averages over p and which, in principle, might let me reach the p^{2/3} mark on average (maybe even $p^{7/12+\varepsilon}$, from a back-of-the-envelope calculation) - I'll have to look into it. – Terry Tao Jul 5 '11 at 2:28
Not that I see immediately how this would help, but do $m$ and $\overline m$ have to be positive for your application, or is it enough to have the least absolute residues be $\widetilde{O}(p^{2/3})$ (again excluding $m = \overline{m} = \pm 1$)? – Noam D. Elkies Jul 5 '11 at 3:17
I'd prefer m and $\overline{m}$ to be positive, but I'll take whatever I can get at this point :-). – Terry Tao Jul 5 '11 at 4:19
Friedlander showed ("Shifted primes without large prime factors") that a positive proportion of $p+1$ are $p^{0.3}$-friable (or so). (It's always quoted as $p-1$, but presumably it works for $p+1$ as well.) That implies that all of those $p+1$ factor as $mn$ where $p^{0.35} < m,n < p^{0.65}$. So a positive proportion of $p$ beat $p^{2/3}$. And then one could always try looking at $2p+1$, $3p+1$, ... or in general starting with the pairs $m,n$ and trying to count how many primes are divisors of some $mn-1$. – Greg Martin Jul 11 '11 at 7:26

The following argument proves that for almost all $p\le x$, there are $m,n\le p^{1/2+\epsilon}$ with $mn\equiv1 \pmod p$.

Indeed, let $$P=\{x/2<p\le x: m\le x^{1/2+\epsilon}\ \implies\ \overline{m}\pmod p>x^{1/2+\epsilon}\}.$$ Let $q$ be a prime in $(x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$. If $1+kp\equiv 0\pmod q$ for some $k\le x^{\epsilon/2}/2$, then $1+kp=qd$ for some $d\le (1+kx)/x^{1/2-\epsilon/2}\le x^{1/2+\epsilon}$. In particular, $p$ is not in $P$. Therefore, if $p$ is counted by $P$, then for each $q\in (x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$, it must avoid the congruence classes $\{-\overline{k}\pmod q: 1\le k\le x^{\epsilon/2}/2\}$. Since $p$ is prime is prime, it must also avoid the classes $0\pmod q$ for all primes $q\le \sqrt{x}$. We then apply the arithmetic form of the Large Sieve (see, e.g., page 159 in Davenport) to conclude that $$\#P \ll \frac{\pi(x)}{x^{\epsilon/2}} ,$$ which proves the claim.

The above result is essentially sharp: the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $o(\pi(x))$ for small enough $c$. Indeed, we would then have that there is some $k\le (\log x)^{2c}$ such that $1+kp$ can be written as $1+kp=mn$ with $m\le n\le x^{1/2}(\log x)^c$. In particular, $1+kp$ would have a divisor $m\in[0.1k\sqrt{x}/(\log x)^c, \sqrt{1+kx}]$. The number of such primes $p\in(x/2,x]$ is $$\asymp f(k) \frac{x}{\log x} \frac{1+\left(\log\frac{(\log x)^{2c}}{k}\right)^\delta}{(\log x)^\delta(\log\log x)^{3/2}},$$ where $\delta=1-(1+\log\log2)/\log 2$ is the constant appearing in Erdos's multiplication table problem and $f(k)$ is some tame multiplicative function that is usually $\asymp1$ (see http://arxiv.org/abs/math/0401223 and http://arxiv.org/abs/0905.0163. This result is not stated there but it should follow from the methods. The upper bound uses the sieve. For the lower bound, instead of the Bombieri-Friedlander-Iwaniec result on primes in APs to large moduli, we would have to use Zhang's result because we need information about the distribution of primes in progressions $a\pmod q$ with $1+ak\equiv0\pmod q$, so $a$ is not fixed.) Summing over $k\le(\log x)^{2c}$, we find that the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $$\ll \frac{x}{\log x} \frac{(\log x)^{2c}}{(\log x)^\delta(\log\log x)^{3/2}} .$$ Taking $c=\delta/2$ yields the claimed result.

The above line of thought should be able to produce, at least heuristically, the optimal value of $c$ for which the following two propositions hold: $$\#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c+\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} \sim \pi(x)$$ and $$\#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c-\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} =o(\pi(x)).$$ The point is that if $k\neq k'$, then the multiplicative structures of $1+kp$ and of $1+k'p$ should be independent from each other. Therefore the events that $1+kp=mn$ for some $m,n$ in some range and that $1+k'p=m'n'$ for some $m',n'$ in some range should be independent. So a Borel-Cantelli argument would then yield the optimal value of $c$.

-
Igor Shparlinski has kindly informed me of some results of very similar flavour that were obtained in math.uiuc.edu/~ford/wwwpapers/fksy.pdf and in math.uiuc.edu/~ford/wwwpapers/Invers-Geom.pdf. There the authors study the quantity $M(n):=\max\{|a-b|:1\le a,b<n,\ ab\equiv1 \pmod n\}$. – Dimitris Koukoulopoulos Nov 26 '14 at 15:02
For a typical $p$ for which $m,\overline m\leq\sqrt p(\log g)^c$ is possible how many such pairs of $m,\overline m$ do you expect? – user76479 May 25 at 21:48

Professor Tao,

I do not know whether this answer is in the least useful but will post it anyway!

I'm not sure but perhaps one approach is via Linnik's theorem that the least prime, say, $p(r,q)$ in an arithmetic progression $r \bmod q$, is $\ll q^L$.

(I actually saw that topic on Math Overflow recently: least prime in a arithmetic progression )

If $p \equiv -b \bmod a$ and $p \equiv -1 \bmod b$, with $(a,b)=1$ and $b$ of size about $a^2$, then one can take

$$m = \frac{p+b}{a}$$

and

$$\overline{m} = \frac{a(p+1)}{b}.$$

But then $p$ is in an arithmetic progression of modulus of size about $a^3$, so

$$\max(m,\overline{m}) \ll p^{1-1/(3L)}.$$

However, currently the state of knowledge of $L$ is not good enough.

EDIT:

Actually, one can take $a,b$ about the same size, $(a,b)=1$, $p\equiv -b \bmod a$ and $p \equiv -a \bmod b$, and

$$m = \frac{p+b}{a}$$

and

$$\overline{m} = \frac{p+a}{b}.$$

Then $p$ is in an arithmetic progression of modulus of size about $a^2$, and

$$\max(m,\overline{m}) \ll p^{1-1/(2L)}.$$

-