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 coefficient, 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 coefficient,
F (N0 + kp) p for every sufficiently 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)
Previous Page Next Page