# 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
show 2 more comments

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)}.$$

-