# Are there infinitely many primes of the form $n^2 - d$, for any $d$ not a square?

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?

-
"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 math.stackexchange.com/questions/4506/… –  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.
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.