On the D. H. Lehmer problem (Q1209033)

Let \(p\) be an odd prime. The author derives an asymptotic formula for the number \(r(p)\) of cases in which \(x\) and \(\overline {x}\) are of opposite parity. Here, \(x\) runs through all integers of the interval \([1,p-1]\), and the element \(\overline {x}\) is given by \(\overline {x}x\equiv 1\mod p\) with \(0<\overline {x}<p\), e.g. for \(p=5\) we have \((x,\overline {x})=(1,1),(2,3),(3,2),(4,4)\), so that \(r(5)=2\). The result reads as follows: \[ r(p)=(p-1)/2+O(p^{1/2}\cdot\log^ 2 p). \] The proof makes use of the Pólya-Vinogradov character sum estimate and of a well-known deep upper bound for the Kloosterman sum \(S(a,b;p)=\sum_{0<x<p} \exp(2\pi i(ax+b\overline {x})/p)\).