Lagrange's theorem implies that for each prime $p$, the factors of $(p − 1)!$ can be arranged in unequal pairs, with the exception of $±1$, where the product of each pair $≡ 1 \pmod p$. See Wiki article on Wilson's theorem.

From the example in the link above, for $p=11$ we have

$$(11-1)!=[(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)] \equiv [-1]\cdot[1\cdot1\cdot1\cdot1] \equiv -1 \pmod{11}$$

Let the products of the pairs that $≡ 1 \pmod p$ be the multiset $A_p$, and $A_{p_n}$ the multiset for the $n$th prime.

For the above example then, $A_{p_5}=\{(2\cdot6),(3\cdot4),(5\cdot9),(7\cdot8)\}=\{12,12,45,56\}$.


$$\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A_{p_n}}(k-1)}{(p_n)^3}\approx\frac18$$

where $p_n$ is the $n$th prime.


For $p=11$ we have


For $p=997$ we have



As @YCor noted below, the $-1$ in the $k-1$ can be removed, since its contribution tends to $0$. The conjecture can therefore be simplified to

$$\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A_{p_n}}k}{(p_n)^3}\approx\frac18$$

I have no idea whether the above statement is correct, or how to go about trying to find a proof. Any comments on the any of the above are most welcome.

  • $\begingroup$ You might as well take that $P_n$ outside the $\sum$. $\endgroup$ Commented Dec 7, 2015 at 11:26
  • 2
    $\begingroup$ You might as well write it as $\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k \in A}k-1}{(p_n)^3}\approx\frac18$. $\endgroup$ Commented Dec 7, 2015 at 11:29
  • $\begingroup$ You can't say $A$ is a set, since you take multiplicities into account. Also you should denote it as $A_p$ and write $A_{p_n}$ instead of $A$ in the conjecture. $\endgroup$
    – YCor
    Commented Dec 7, 2015 at 11:46
  • 1
    $\begingroup$ It might help to note that $\lim\limits_{n\rightarrow\infty}\dfrac{\sum\limits_{k=2}^{n/2}k(n-k)-1}{n^3} = \frac{1}{12}$. $\endgroup$ Commented Dec 7, 2015 at 11:58
  • 1
    $\begingroup$ With @YCor's notation, if it's reasonable to assume that $i$ and $c_i$ behave roughly independently then one would have $\frac1p \sum i c_i \approx \left(\frac1p \sum i\right) \left(\frac1p \sum c_i\right) \approx p^2/4$, so this heuristically justifies the $1/8$. $\endgroup$ Commented Dec 7, 2015 at 12:05

2 Answers 2


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^2 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.

  • 4
    $\begingroup$ How can you get $O(\sqrt{p}\log p)$? I can prove asymptotic formula only with $O(\sqrt{p}\log^2 p)$. $\endgroup$ Commented Dec 10, 2015 at 2:20
  • 1
    $\begingroup$ You are right, I was thinking in one dimension. I corrected the error term to $\mathcal{O}(\sqrt{p}\log^2 p)$. $\endgroup$ Commented Dec 10, 2015 at 22:08
  • $\begingroup$ But your error term can be valid. In the question mathoverflow.net/questions/175822/incomplete-kloosterman-sum the error term was $O(\sqrt{p}\log p)$ indeed. In the case $f(x,y)=xy$ situation can be similar. $\endgroup$ Commented Dec 12, 2015 at 4:49
  • $\begingroup$ @AlexeyUstinov certainly $O(\sqrt{p}\log p)$ looks feasible: plot 1, plot 2 where first plot is $\left(\left(p_n/2\right)^3-\sum\limits_{k \in A_{p_n}}{k}\right)/\left(p_n^{5/2}\log p_n\right),$ second is $ \text{expr.} ~/\left(p_n ^{5/2}\log^{2} p_n\right).$ $\endgroup$
    – martin
    Commented Dec 14, 2015 at 12:34
  • 1
    $\begingroup$ @martin Thank you for calculations, probably $O(\sqrt p\log p)$ is a right order for error term. $\endgroup$ Commented Dec 14, 2015 at 12:41

If $f(x,y)$ is a "good" function, then $$\sum_{xy\equiv 1\mod p}f(x,y)=\frac{1}{p}\sum_{x,y=0}^{p-1}f(x,y)-R_p[f],$$ where $R_p[f]$ is a "small" error term (see Lemma 5 here). In your case $f(x,y)=xy$, so the main term is $p^3/4.$ Usually $R_p[f]=O(p^{1/2+\varepsilon}\|f\|)$ while the main term is like $p\|f\|$. In this case error term is $O(p^{5/2+\varepsilon}).$

This observation has a lot of applications in problems connected with lattices (because bases are parametrized by equation $ad-bc=n$, so $ad\equiv n\mod b$ ).

  • $\begingroup$ thanks for the great answer! So in this case $$\left(p_n/2\right)^3-\sum\limits_{k \in A_{p_n}}{k}=\mathcal{O}\left(p_n\ ^{5/2}\right)$$? $\endgroup$
    – martin
    Commented Dec 8, 2015 at 18:51
  • 1
    $\begingroup$ Yes. But it must be $O(p_n^{5/2}\log^2p_n)$ instead of $O(p_n^{5/2})$. $\endgroup$ Commented Dec 9, 2015 at 2:12
  • 1
    $\begingroup$ And this $\log$ is impotant because usually (numerically, it is not proved) normalized error term (in our case $R_p\cdot p^{-5/2}$) is gaussian i.e. unbounded. $\endgroup$ Commented Dec 9, 2015 at 3:08
  • 1
    $\begingroup$ @Jose Brox The "history" goes back to the theory of numerical integration and uniform distribution theory. When you replace given function $f$ by its Fourier series you'll get error term depending on Fourier corfficients of $f$ and trigonometric sums of a given net. This argument was used by Weyl in his pioneer work Über die Gleichverteilung von Zahlen mod. Eins (1916). Basic latice problem is a distribution of vectors in reduced basis. Conditions from Lemma 5 can be replaced for another ones (see the proof). $\endgroup$ Commented Jan 29, 2018 at 11:25
  • 1
    $\begingroup$ @JoseBrox I applied this technique in Frobenius problem, see 1 and 2. Reduction of Frobenius problem to a lattice proble is described here. $\endgroup$ Commented Feb 2, 2018 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.