Return to Revisions

For an integer $n$ with $1\leq n\leq p-1$, let $n^{-1}$ be the inverse of $n$ modulo $p$. It follows from Weil's bound on Kloosterman sums that for every $\epsilon>0$ the set $\{n: xp\leq n\leq (x+\epsilon) p, yp\leq n^{-1}<(y+\epsilon) p\}$ has cardinality $\epsilon^2p+\mathcal{O}(\sqrt{p}\log p)$. Hence up to a relative error tending to 0 the sum in question can be replaced by an integral, that is $$ \sum_{n=1}^{p-1} n\cdot n^{-1} \sim p^3\int_0^1\int_0^1 xy\;dx\;dy = \frac{p^3}{4}. $$ (Note that the $\cdot$ on the left hand side refers to the multiplication of integers, not to modular multiplication). Here each pair $(a,b)$ with $ab\equiv 1\pmod{p}$ is counted twice, with the exception of $(1,1)$ and $(-1, -1)$, which contribute less than $p^2$. Hence up to an error $\mathcal{O}(p^2)$ the left hand side of the above expression is twice $\sum_{k\in A} k$, which proves your claim.