18 1. Elementary Prime Number Theory, I

This shows that every prime divisor of

n2

+ n + A exceeds its square root,

so that

n2

+ n + A is prime.

The proof of the remaining implication requires one more preliminary

result:

Lemma 1.13. If π is an element of Z[η] whose norm is a rational prime p,

then π is prime in Z[η].

Proof. We claim that Z[η]/(π) is isomorphic to Z/pZ. Since Z/pZ is a

field, this implies that π generates a prime ideal of Z[η], which in turn

implies that π is prime. Let ψ : Z → Z[η]/(π) be the ring homomorphism

defined by mapping n to n mod π. Since p = ππ ≡ 0 (mod π), the kernel of

ψ contains the ideal pZ. Since pZ is a maximal ideal, either ψ is identically

zero or the kernel of ψ is precisely pZ. Since π is not a unit in Z[η], ψ(1) is

nonzero, and so the kernel of ψ is precisely pZ. Hence Z/pZ is isomorphic to

the image of ψ. So the proof will be complete if we show that ψ is surjective.

Write π = r + sη for integers r and s, and let x + yη be an arbitrary

element of Z[η]. We can choose integers a and b for which

m := x + yη − π(a + bη) ∈ Z.

Indeed, a short computation shows that this containment holds precisely

when

b(r − s) + as = y,

which is a solvable linear Diophantine equation in a and b since gcd(r−s, s) =

gcd(r, s) = 1. Then m ≡ x + yη (mod π), and so ψ(m) = x + yη mod π.

Since x + yη was arbitrary, ψ is surjective as claimed.

Proof that (ii) ⇒ (iii). Suppose that

n2

+ n + A is prime for all

0 ≤ n ≤

1

2

|D|

3

−

1

2

.

We are to prove that Z[η] possesses unique factorization. Suppose other-

wise, and let α be a nonzero, nonunit of minimal norm with two distinct

factorizations into irreducibles, say

α = π1 · · · πk = ρ1 · · · ρj.

(Here distinct means that either k = j, or that k = j, but there is no

way to reorder the πi so that each πi is a unit multiple of ρi.) By the

minimality of N (α), it is easy to see that none of the irreducibles in the

first factorization can be a unit multiple of an irreducible in the second

factorization. Consequently, none of the irreducibles appearing in either

factorization can be prime in Z[η].