22 1. Elementary Prime Number Theory, I

the

60◦

angle determined by e1 and e2, we find that

|(n − 1) + 1/2| = |n − 1/2| ≤

1

2

|D|/3.

But now (ii) of Theorem 1.10 implies that

N (ξ) =

n2

− n + A

= (n −

1)2

+ (n − 1) + A

is prime, so that ξ is a prime element of Z[η] by Lemma 1.13.

A small amount of computation shows that condition (ii) of Theorem

1.10 holds for the values A = 2, 3, 5, 11, 17, and 41. This yields the following

corollary:

Corollary 1.14. Z[(−1+

√

D)/2] is a unique factorization domain for D =

−7, −11, −19, −43, −67, −163.

Checking larger values of A does not appear to yield any more examples

satisfying the conditions of Theorem 1.10. Whether or not the list in Corol-

lary 1.14 is complete is known as the class number 1 problem; an equivalent

question appears in Gauss’s Disquisitiones (see [Gau86, Art. 303]). In

1933, Lehmer showed [Leh33] that any missing value of A is necessarily

large, in that |D| 5 ·

109.

In 1934, Heilbronn & Linfoot [HL34] showed

that there is at most one missing value of A. Finally, in 1952, Heegner settled

the problem, using new techniques from the theory of modular functions:

Theorem 1.15 (Heegner). If A 41, then Z[η] does not have unique fac-

torization. Hence if A ≥ 2 is an integer for which

n2

+ n + A is prime for

all 0 ≤ n A − 1, then A ≤ 41.

For a modern account of Heegner’s proof, see [Cox89, §12].

9. Primes represented by general polynomials

The result of the previous section leaves a very natural question unresolved:

Does Euler’s polynomial T

2

+ T + 41, which does such a marvelous job of

producing primes at the first several natural numbers n, represent infinitely

many primes as n ranges over the set of all positive integers? More generally,

what can one say about the set of prime values assumed by a polynomial

F (T) ∈ Z[T]? In this section we survey the known results in this direction.

9.1. The linear case. Suppose first that F (T) is linear, say F (T) = a +

mT, where m 0. Asking whether F (n) is prime for infinitely many natural

numbers n amounts to asking whether the infinite arithmetic progression

a + m, a + 2m, a + 3m, a + 4m, . . .