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
+ 1. If p divides
+ 1, then
−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
+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
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
+ 1 and Φ3(T) = T
+ 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-
Proof. For each m we have the factorization
− 1 =
To see this, note that T
− 1 =
(T − ζ). Since the set of mth roots
of unity is the disjoint union of the primitive dth roots of unity, taken over