8. Euler’s prime-producing polynomial 15

any function which produces only primes cannot have too simple a form.

We give only one early example of a result in this direction. (See [War30],

[Rei43] for more theorems of this flavor.)

Theorem 1.9 (Goldbach). If F (T) ∈ Z[T] is a nonconstant polynomial

with positive leading coeﬃcient, then F (n) is composite for infinitely many

natural numbers n.

Proof. Suppose F is nonconstant but that F (n) is prime for all n ≥ N0,

where N0 is a natural number. Let p = F (N0); then p divides F (N0 + kp)

for every positive integer k. But since F has a positive leading coeﬃcient,

F (N0 + kp) p for every suﬃciently large integer k, and so F (N0 + kp) is

composite, contrary to the choice of N0.

Theorem 1.9 does not forbid the existence of polynomials F which as-

sume prime values over impressively long stretches. And indeed these do

exist; a famous example is due to Euler, who observed that if f(T) =

T

2

+ T + 41, then f(n) is prime for all integers 0 ≤ n 40.

It turns out that Euler’s observation, rather than being an isolated cu-

riosity, is intimately connected with the theory of imaginary quadratic fields.

We will prove the following theorem:

Theorem 1.10. Let A ≥ 2, and set D := 1 − 4A. Then the following are

equivalent:

(i)

n2

+ n + A is prime for all 0 ≤ n A − 1,

(ii)

n2

+ n + A is prime for all 0 ≤ n ≤

1

2

|D|

3

−

1

2

,

(iii) the ring Z[(−1 +

√

D)/2] is a unique factorization domain.

The equivalence (i) ⇔ (iii) is proved by Rabinowitsch in [Rab13], and

is usually referred to as Rabinowitsch’s theorem.

Remark. Since

n2

+ n + A = (n

+1/2)2

+(4A − 1)/4, (ii) can be rephrased

as asserting that (n +

1/2)2

+ |D|/4 is prime for every integer n for which

|n + 1/2| ≤

1

2

|D|

3

. We will use this observation in the proof of Theorem

1.10.

Cognoscenti will recognize that Z[(−1 +

√

D)/2] is an order in the qua-

dratic field Q(

√

D). However, the proof of Theorem 1.10 presented here, due

to Gyarmati (n´ ee Lanczi) [L´ an65], [Gya83] and Zaupper [Zau83], requires

neither the vocabulary of algebraic number theory nor the theory of ideals.

We begin the proof of Theorem 1.10 by observing that the bound on

n in (ii) is always at least as strict as the bound on n in (i), which makes

clear that (i) implies (ii). So it is enough to show that (ii) implies (iii)