Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I tried to compute the multiplicative inverse of the probability that $ 2 x^2 +1 $ is prime.
(I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for now).
I know it should be around $2 \log(x) - 1$ from the PNT.
Using the sieve $(1-1/2)(1-1/3)(1-1/5) ... (1-1/p)$ over the primes $p$ we get $O(\log(x))$ actually $2C\log(x)$ with $C$ mertens constant. This is slightly worse but $C$ is not so far from $1$.

However when I tried differently I got confused.

I tried to sieve by using quadratic residues.

Let $p_n*$ be a prime such that it has a solution $x$ to $2 x^2 + 1 = 0 \pmod p$.

I believe that probability is about $1/2$.

Then I sieve : $(1-1/2)(1-1/p_1*)(1-1/p_2*)...(1-1/p_n*)$

And consider the worst case and average scenarios.

This does not agree well with $2 \log(x)$ even after dividing by $C$!??

What did I do wrong?

share|cite|improve this question
I removed the tag residue-calculus, which is something else. When a tag doesn't have a tag wiki, you may be able to tell from other questions tagged with it what it's about. – joriki Oct 12 '12 at 15:53
I did not find tag quadratic residue , I guess I took the complex analysis residue tag hmm Sorry and thanks. – mick Oct 12 '12 at 15:55
I don't understand the reasoning behind your sieve; could you explain? Also, the $O(\log x)$ probability doesn't come out directly from $\prod_n(1-1/p_n)$, since it's not obvious where to cut the product off; how did you do this for your sieve? – joriki Oct 12 '12 at 15:56
The lack of understanding of the reasoning behind your sieve that I expressed is more fundamental than that. You've offered no reasons to think that the product you wrote down should yield the desired probability. – joriki Oct 12 '12 at 16:12
@mick This does not explain any of your terms $(1-1/p_n^*)$ nor even the initial $(1-1/2)$ term. What is the probability that $2x^2+1$ is 0 mod 3? – Erick Wong Oct 12 '12 at 16:20
up vote 1 down vote accepted

If I understand your thoughts behind this approach correctly, then the error lies in taking into account that some primes don't allow solutions but not taking into account that for the remaining primes the probability of $2x^2+1$ being composite is doubled. That is, either $-2^{-1}$ is a quadratic residue mod $p$ or not; if it isn't, the probability for $2x^2+1$ to be divisible by $p$ is $0$, but if it is, then it's $2/p$, since there are two different residues for $x$ that satisfy the equation.

Also, even if your approach had been right, there wouldn't have been any contradiction; it's perfectly possible for some forms of numbers to have a different probability of being prime if you take their special form into account than if you don't. As an extreme case, you can calculate the probability for $2x$ to be prime as $1/\log(2x)$, but of course if you take the form of $x$ into account it's zero. As a less extreme case, $2^n-1$ has a non-zero probability of being prime that's different from $1/\log(2^n-1)$ if you take its form into account, since the residues follow periodic patterns.

share|cite|improve this answer
Thanks for the answer , and yes you got it right. 2 comments : 1) if its 2/p than $(1-1/2)(1-2/p_1*)(1-2/p_2*)$... should be the correct sieve ?? 2) your comforting talk about $1/log(2x)$ is sweet :) , however I know in this case that the probability is $1/(2 log(x) -1)$ and that is a big difference ! – mick Oct 12 '12 at 18:29
@mick: 1) I think so. 2) What does that mean? As far as I'm aware, that probability is only defined asymptotically; in what sense is the probability $1/(2\log x-1)$? (By the way, you can get proper formatting for the log (or any similar function like sin and exp) using \log.) – joriki Oct 12 '12 at 18:59
at 1) you answered : I think so. I ofcourse would like to see a proof. It seems like an interesting identity if true. – mick Oct 12 '12 at 19:04
...even if just approximately or statisticly true... – mick Oct 12 '12 at 19:05
@mick: I don't know how to prove such a thing beyond the arguments that we've already discussed. – joriki Oct 12 '12 at 19:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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