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

Clearly, for $d$ a square number, there is at most one prime of the form $n^2 - d$, since $n^2-d=(n+\sqrt d)(n-\sqrt d)$.

What about when $d$ is not a square number?

share|cite|improve this question
"Clearly, for $d$ a square number, there is only one prime..." - I don't see any primes for $d = 16$. – TMM May 12 '12 at 20:16
@TMM, updated to be "at most one prime" – mike May 12 '12 at 20:28
It would be surprising if this were known. Nobody knows whether there are infinitely many primes $n^2 + 1$ and there is no resolution of the problem in sight. – Will Jagy May 12 '12 at 20:38
See the answer to this question… – Zander May 14 '12 at 20:31
@Will, everybody knows that there are infinitely many primes of the form $n^2+1$, it's just that nobody knows how to prove it. – Gerry Myerson May 19 '12 at 9:14

There's a host of conjectures that assert that there an infinite number of primes of the form $n^2-d$ for fixed non-square $d$. For example Hardy and Littlewood's Conjecture F, the Bunyakovsky Conjecture, Schinzel's Hypothesis H and the Bateman-Horn Conjecture.

As given by Shanks 1960, a special case of Hardy and Littlewood's Conjecture F, related to this question, is as follows:

Conjecture: If $a$ is an integer which is not a negative square, $a \neq -k^2$, and if $P_a(N)$ is the number of primes of the form $n^2+a$ for $1 \leq n \leq N$, then \[P_a(N) \sim \frac{1}{2} h_a \int_2^N \frac{dn}{\log n}\] where $h_a$ is the infinite product \[h_a=\prod_{\text{prime } w \text{ does not divide } a}^\infty \left(1-\left(\frac{-a}{w}\right) \frac{1}{w-1}\right)\] taken over all odd primes, $w$, which do not divide $a$, and for which $(-a/w)$ is the Legendre symbol.

The integral is (up to multiplicative/additive constants) the logarithmic integral function.

share|cite|improve this answer

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.