# Finding Gaussian Primes along Lines in $\mathbb Z[i]$

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$:

%pylab
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)

plot(a,b,'b.')

• 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? – Romain S Jul 7 '15 at 2:10
• @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. – Chris Swierczewski Jul 7 '15 at 14:03

" There are an infinite number of primes of the form $n^2+1$ "
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]$.