I am trying to prove the following statement:

For all positive integers $a$ does there exists a positive integer $b$ such that $a^2 + b^2$ is prime? (If so, can we provide such a $b$?)

Given the connection between primes of this form and Gaussian primes, the above problem leads to the lemma:

Given a positive integer $a$ does there exist a positive integer $b$ such that $a+bi$ is a Gaussian prime. (If so, can we provide such a $b$?)

Based on the pictures generated of Gaussian primes, such as the ones shown in A Stroll Through Gaussian Primes, it seems to the case that this statement is true. (The pictures suggest that every vertical line in $\mathbb{Z}[i]$ contains at least one Gaussian prime.)

My current approach, which is somewhat of a longshot, goes as follows: a Gaussian integer $z = a+bi$ is a Gaussian prime if and only if $N(z) := a^2 + b^2$ is prime. Given some $a$, consider the Gaussian integers

$$z_n = a + ni, \quad n=0, \ldots, a,$$

and the corresponding norms

$$N_n := N(z_n) := a^2 + n^2, \quad n=0, \ldots, a.$$

These norms range between $N_0 = a^2$ and $N_a = 2a^2$. By Bertrand's Postulate, there exists some prime $p$ within that range of norms. The part that I was hoping could be proven is that there exists some prime $p$ such that $p = N(z_n)$ for some $n$.

Finally, here is a little Python code demonstrating that this is true for $a = 1, \ldots, 100000$:

from sympy import isprime
from itertools import ifilter

def find_b(a):
    """Returns smallest b such that a^2 + b^2 is prime."""
    f = lambda b: isprime(a**2 + b**2)
    g = ifilter(f, itertools.count())
    b = g.next()
    return b

a = range(1, 100000)
b = map(find_b, a)

  • $\begingroup$ Fermat's theorem on the sum of two squares states that every prime p satisfies the equation $p=x^2+y^2$ for integers x and y iff $p=1(mod4)$. Is it possible to use that in order to prove your statement? $\endgroup$
    – Romain S
    Jul 7 '15 at 2:10
  • $\begingroup$ @Romain You can use this to show relationships such as if $a \equiv 0,2 \pmod{4}$ then $b \equiv 1,3 \pmod{4}$ and vice versa. I think the primary difference between this problem and Fermat's theorem is that we don't know $p$ ahead of time. $\endgroup$ Jul 7 '15 at 14:03

It is an exceptionally difficult problem. For instance, the Landau conjecture:

" There are an infinite number of primes of the form $n^2+1$ "

is still a conjecture.

Iwaniec, Friedlander and Heath-Brown have proved that there is an infinite number of primes of the form $a^2+b^4$ and $a^3+2b^3$ through Bombieri's asymptotic sieve, while Tao has proved the existence of arbitrarily shaped prime constellations in $\mathbb{Z}[i]$.

Your conjecture is extremely likely to hold: however, it is extremely difficult to tackle, too.

  • $\begingroup$ I read your response after further investigation of my own and have come to the same conclusion. Thank you very much for your input and mentions of similar problems! $\endgroup$ Jul 8 '15 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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