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 + 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
+ n + A is prime for all 0 ≤ n A − 1,
+ n + A is prime for all 0 ≤ n ≤
(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.
+ n + A = (n
+(4A − 1)/4, (ii) can be rephrased
as asserting that (n +
+ |D|/4 is prime for every integer n for which
|n + 1/2| ≤
. We will use this observation in the proof of Theorem
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)