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