9. Primes represented by general polynomials 23
contains infinitely many primes — or, phrased in terms of congruences,
whether or not there are infinitely many primes p ≡ a (mod m).
This question is sometimes easy to answer. Let d = gcd(a, m). If d 1,
then there are at most finitely many primes in the above progression, since
every term is divisible by d, and so we have a negative answer to our query.
So let us suppose that d = 1. Then certain special cases can easily be settled
in the aﬃrmative. For example, if a = −1 and m = 4, then we are asking
for infinitely many primes p ≡ −1 (mod 4), and now we can mimic Euclid:
If there are only finitely many such primes, say p1,...,pk, form the number
N := 4p1 · · · pk − 1. Since N ≡ −1 (mod 4), it must have at least one prime
divisor p ≡ −1 (mod 4). But p cannot be any of p1,...,pk, and we have a
contradiction. A similar argument works when a = −1 and m = 3.
The general case of our problem is much more diﬃcult. It turns out that
whenever gcd(a, m) = 1, there are infinitely many primes p ≡ a (mod m).
This was proved by Dirichlet in 1837, by analytic methods. (One can view
his argument as a far-reaching generalization of Euler’s proof that the sum
of the reciprocals of the primes diverges.) We will give a proof of Dirichlet’s
theorem in Chapter 4.
For now we content ourselves with some special cases of Dirichlet’s the-
orem that follow from algebraic arguments. We noted above that an easy
variant of Euclid’s proof shows that there are infinitely many primes p for
which the residue class of p avoids the trivial subgroup of the unit group
and similarly for
As observed by A. Granville (unpub-
lished), we have the following general result:
Theorem 1.16. If H is a proper subgroup of
then there are
infinitely many primes p for which p mod m ∈ H.
Proof. Let P be the set of primes p for which p mod m ∈ H, and let P
be the set of such primes not dividing m. Assuming P is finite, let P be
the product of the elements of P . Fix an integer a coprime to m with
a mod m ∈ H (which is possible since H is a proper subgroup), and then
choose a positive integer n satisfying the congruences n ≡ 1 (mod P ) and
n ≡ a (mod m). (Such a choice of n is possible by the Chinese remainder
theorem.) Since n is coprime to mP , none of its prime divisors can come
from P, so that every prime p dividing n must be such that p mod m ∈ H.
But since H is closed under multiplication, this implies that n mod m ∈ H.
This contradicts the choice of a.
If F (T) is a nonzero polynomial with integer coeﬃcients, we say that
the prime p is a prime divisor of F if p divides F (n) for some integer n. The
following useful lemma is due to Schur [Sch12]: