8. Euler’s prime-producing polynomial 17

Lemma 1.11. An element α ∈ Z[η] is a unit precisely when N (α) = 1.

The only units in Z[η] are ±1.

Proof. If α is a unit, then N (α) · N

(α−1)

= 1. Moreover, both N (α) and

N (α−1) are positive integers, so that N (α) = N (α−1) = 1. Conversely, if

N (α) = 1, then αα = 1, and so α is a unit. Finally, notice that if y = 0,

then

N (x + yη) =

x2

− xy +

Ay2

= (x −

y/2)2

+

1

4

(4A −

1)y2

≥

4A − 1

4

7

4

1.

So x + yη can be a unit only when y = 0. In this case we must have

N (x) =

x2

= 1, and this occurs exactly when x = ±1.

Lemma 1.12. If α is a nonzero, nonunit element of Z[η], then α can be

written as a product of irreducible elements of Z[η].

Proof. If the claim fails, there is a nonzero, nonunit α of smallest norm

for which it fails. Clearly α is not irreducible, and so we can write α = βγ,

where β and γ are nonzero nonunits. Hence N (α) = N (β)N (γ). Since N (β)

and N (γ) are each larger than 1, both N (β) and N (γ) must be smaller than

N (α). So by the choice of α, both β and γ factor as products of irreducibles,

and thus α does as well. This contradicts the choice of α.

We can now prove one of the two outstanding implications:

Proof that (iii) ⇒ (i). Let η = (−1 +

√

D)/2. Suppose 0 ≤ n A − 1.

We have

(1.9)

n2

+ n + A = (n − η)(n − ¯) η = (n − η)(n + 1 + η).

Let p be a prime dividing

n2

+ n + A. We claim that p is not irreducible in

Z[η]. Indeed, since Z[η] is a unique factorization domain by hypothesis, if p

were irreducible, then p would be prime. So from (1.9), we would have that

p divides n − η or n + 1 + η. But this is impossible, since neither n/p − η/p

nor (n + 1)/p + η/p belongs to Z[η] = Z + Zη.

Hence we can write p = αβ, where α, β ∈ Z[η] and neither α nor β is a

unit. Taking norms, we deduce that

p2

= N (p) = N (α)N (β). Since α and

β are not units, we must have N (α) = N (β) = p.

Write α = x + yη for integers x, y. Then y = 0 (since p is a rational

prime), and so

p = N(α) =

x2

− xy +

Ay2

= (x −

y/2)2

+ (A −

1/4)y2

≥ A − 1/4.

Thus (since p is an integer) p ≥ A. Moreover, since 0 ≤ n A − 1,

n2

+ n + A (A −

1)2

+ (A − 1) + A = (A − 1)A + A =

A2.