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

(Z/4Z)×,

and similarly for

(Z/3Z)×.

As observed by A. Granville (unpub-

lished), we have the following general result:

Theorem 1.16. If H is a proper subgroup of

(Z/mZ)×,

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]: