24 1. Elementary Prime Number Theory, I

Lemma 1.17. Let F (T) be a nonconstant polynomial with integer coeﬃ-

cients. Then F has infinitely many prime divisors.

Proof. If F (0) = 0, then every prime is a prime divisor of F . So we

can assume that the constant term c0 (say) of F (T) is nonzero. Then

F (c0T) = c0G(T) for some nonconstant polynomial G(T) with constant

term 1. It is enough to show that G has infinitely many prime divisors.

Suppose that p1,...,pk is a list of prime divisors of G. For m suﬃciently

large, we have |G(mp1 · · · pk)| 1, so that there must be some prime p di-

viding G(mp1 · · · pk). Then p is a prime divisor of G and p is not equal to

any of the pi, since G(mp1 · · · pk) ≡ 1 (mod pi) for each 1 ≤ i ≤ k. So no

finite list of prime divisors of G can be complete.

For example, let F (T) = T

2

+ 1. If p divides

n2

+ 1, then

n2

≡

−1 (mod p), and so either p = 2 or p ≡ 1 (mod 4). So Lemma 1.17

implies that there are infinitely many primes p ≡ 1 (mod 4). Similarly, if

F (T) = T

2

+T +1, then any prime divisor p of F is such that p ≡ 1 (mod 3),

and so there are infinitely many primes p ≡ 1 (mod 3). Combining this with

our earlier results, we have proved Dirichlet’s theorem for all progressions

modulo 3 and modulo 4.

These examples are special cases of the following construction: Recall

that the mth cyclotomic polynomial is defined by

Φm(T) =

1≤k≤m

gcd(k,m)=1

T −

e2πik/m

,

i.e., Φm(T) is the monic polynomial in C[T] whose roots are precisely the

primitive mth roots of unity, each occurring with multiplicity 1. For exam-

ple, Φ4(T) = T

2

+ 1 and Φ3(T) = T

2

+ T + 1.

We will apply Lemma 1.17 to Φm to deduce that there are infinitely

many primes p ≡ 1 (mod m). To apply Lemma 1.17, we need that the

coeﬃcients of Φm(T) are not merely complex numbers, but in fact integers.

Lemma 1.18. For each positive integer m, the polynomial Φm(T) has in-

teger coeﬃcients.

Proof. For each m we have the factorization

(1.11) T

m

− 1 =

d|m

Φd(T).

To see this, note that T

m

− 1 =

ζm=1

(T − ζ). Since the set of mth roots

of unity is the disjoint union of the primitive dth roots of unity, taken over