Skip to main content
4 of 6
Corrected a few typos and things. Added stuff too.; added 5 characters in body
Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106

This answer is a heuristic along the lines of Joro's.

We use $p,q,r$ to denote primes. Let $S(p,a)$ denote the number of pairs of primes $(q,r)$ with $q,r\leq p$ and $p|(qr+a)$. We are interested in the case $a=1$, but in general by the orthogonality relations of the characters we have $$ S(p,a)=\frac{1}{\phi(p)}\sum_{r\leq p}\sum_{q\leq p}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\chi\left(qr\right).\ \ \ \ \ \ \ \ \ \ (1)$$ Rearranging this is $$S(p,a)=\frac{1}{p-1}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\left(\sum_{q\leq p}\chi\left(q\right)\right)^{2}.$$

We might hope, as is the often the case, that the sums are all very small except when $\chi$ is principle, and that only the principle character contributes. With this in mind we expect

$$S(p,a)\approx \frac{1}{p} \text{li}(p)^2.$$

This is the same as conjecturing that $S(p,a)$ does not vary largely between $a$. In particular, if we average over all $a$ modulo $p$, then using (1) along with the orthogonality relation $\sum_{a\text{ mod } p}\sum_{\chi\text{ mod } p}\chi (a)=\phi(p)$, we see that $$\frac{1}{\phi(p)}\sum_{a\text{ mod } p} S(p,a)=\frac{1}{p-1}\sum_{r\leq p}\sum_{q\leq p}1=\pi(p)^2\sim \frac{1}{p}\text{li}(p)^2.$$

Numerically this is remarkably close for $a=1$. Using the calculation done in Joro'sanswer, letting $a=1$ and $p=1000003$ we have $$S(p,1)=6184$$ whereas $$\frac{1}{p} \text{li}(p)^2=6182.307\dots $$

Now all that remains is to understand the sum $$\sum_{q\leq p}\chi\left(q\right)$$ for a character modulo $p$. However, I believe this is very difficult.

Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106