Dirichlet’s Theorem on Primes in an Arithmetic Progression

Daniel Weissman

May 24, 2004

1 Introduction and References

Our goal is to prove the following theorem: Dirichlet’s Theorem: For any coprime a, b ∈ Z, there are infinitely many primes p such that p ≡ a (mod b).

Although the statement of the theorem involves only integers, the simplest proof requires the use of complex numbers and Dirichlet L-series. Most of this paper will therefore be devoted to proving some basic properties of characters and L-series, after which the desired theorem will follow fairly easily.

The main sources for the following proof are Daniel Marcus’ Number Fields and Chapter 7 from Chan Heng Huat’s online course notes from MA 4263: Analytic Number Theory at the National University of Singapore (available at http://www.math.nus.edu.sg/˜ chanhh/MA4263/MA4263.html), especially the latter. Marcus proves a more general result, while Chan’s proof is a little easier to follow. In addition, our proof that ∑_{p} \frac{1}{p^{s}} diverges as s → 1^{+} is based on arguments in Joseph Bak and Donald Newman’s Complex Analysis, and the discussion of Chebotarev’s Density Theorem follows H. P. F. Swinnerton-Dyer’s A Brief Guide to Algebraic Number Theory. The latter book also contains a proof of Dirichlet’s Theorem, but Swinnerton-Dyer is not as easy to understand as Marcus and Chan.

For those who would like to read a little more about the subject, Atle Selberg’s “An Elementary Proof of Dirichlet’s Theorem About Primes in an Arithmetic Progression” (The Annals of Mathematics, Vol. 50, No. 2 (Apr., 1949), 297-304) proves the theorem without using complex numbers. However, the proof is long and not particularly enlightening. (I also think that the techniques probably do not generalize as well as the ones used in our proof.) The more general Chebotarev Density Theorem is proved in Swinnerton-Dyer (although I do not know how understandable the proof is), and Marcus provides the outlines of a proof and leaves the rest as an exercise.

2 Characters

We will define characters for finite abelian groups. They can be defined for general groups, but our proof will only use the characters of the group (Z/bZ)^{∗}, so this definition will be sufficient.

Definition: A character χ of a finite abelian group G is a homomorphism χ : G → C^{∗} taking G to the unit circle. Note that the characters of a finite abelian group are exactly the one-dimensional group representations. The characters of more general groups do not have this property.

The finite multipicative subgroups of C^{∗} are just the n^{th} roots of unity, so each character maps G to the n^{th} roots of unity for some n ≥ 1. Note that since χ is a group homomorphism, its kernel is a subgroup H ⊂ G, and it maps each H-coset of G to a distinct root. It therefore maps an equal number of elements of G to each root of unity.

We define multiplication of characters by

χχ′ : g ↦ χ(g)χ′(g).  (1)

Note that with this definition of multiplication, the characters form a group, which is usually called Ĝ. We will denote the identity element (which maps G to 1) by χ_{0}. Note also that, because the characters map to the unit circle, χ^{−1}(g) = 1/χ(g) = \overline{χ(g)}, the complex conjugate of χ(g). We will therefore write the inverse of χ as χ̄. One important property of the character group is that it is isomorphic to G.

Lemma: Ĝ ≅ G.

Proof: Since G is a finite abelian group, we can write

G ≅ Z/(d_{1}) ⊕ Z/(d_{2}) ⊕ … ⊕ Z/(d_{k})  (2)

with d_{1}|d_{2}| … |d_{k}. We can write each element of G as (e_{1}, …, e_{k}), e_{i} ∈ Z/(d_{i}). G will be generated by a_{1} = (1, 0, …, 0), a_{2} = (0, 1, 0, …, 0), …, a_{k} = (0, 0, …, 0, 1), with each a_{i} having order d_{i}. Each character χ must map each a_{i} to one of the d_{i}^{th} roots of unity. If we let ζ_{d_{i}} = e^{2πi/d_{i}}, then χ(a_{i}) = ζ_{d_{i}}^{e_{i}}, e_{i} ∈ Z/(d_{i}). Each χ will be determined by its values on the a_{i}, so we can specify χ by the k-tuplet (e_{1}, …, e_{k}). Any possible sequence of values for the e_{i} defines a valid character, so there is an obvious bijection between G and Ĝ. This bijection clearly respects the group law.

Corollary: The characters satisfy two important identities:

(i) ∑_{g∈G} χ(g) = \{ \begin{matrix}|G| & if χ = χ_{0}; \\ 0 & otherwise \end{matrix}  (3)

(ii) ∑_{χ∈Ĝ} χ(g) = \{ \begin{matrix}|G| & if g = 1; \\ 0 & otherwise. \end{matrix}  (4)

Proof: (i) This follows immediately from the fact that χ sends an equal number of elements of G to each d^{th} root of unity, and that the sum of the d^{th} roots of unity is 0 for d > 1.

(ii) If g = 1, then χ(g) = 1 for all χ, so ∑_{χ∈Ĝ} χ(g) = |Ĝ| = |G|. (|Ĝ| = |G| since Ĝ ≅ G.) If g ≠ 1, then ∃χ_{1} ∈ Ĝ such that χ_{1}(g) ≠ 1. (Otherwise, Ĝ, and thus also G, would be the trivial group, and we would not be able to find an element g ≠ 1.) We can write

∑_{χ∈Ĝ} χ(g) = ∑_{χ∈Ĝ} χ_{1}χ(g)
= χ_{1}(g) ∑_{χ∈Ĝ} χ(g),

so we must have ∑_{χ∈Ĝ} χ(g) = 0.

3 Dirichlet L-series

If G = (Z/bZ)^{∗}, then we can extend the characters of G to all n ∈ Z by letting

χ(n) = \{ \begin{matrix}χ(n̄) & if n̄ ∈ (Z/bZ)^{∗}; \\ 0 & otherwise, \end{matrix}

where n̄ is the residue class of n (mod b). Note that these Dirichlet characters form a group canonically isomorphic to Ĝ, so all the results proved in the previous section carry over in the obvious ways. For the rest of the paper, we will use “character,” “χ,” and “Ĝ” to refer to the Dirichlet characters of G = (Z/bZ)^{∗}. Note that with this definition we have |G| = ϕ(b), where ϕ is Euler’s function.

The Dirichlet L-series is then defined for s ∈ C and χ ∈ Ĝ by

L(s, χ) = ∑_{n=1}^{∞} \frac{χ(n)}{n^{s}}.  (5)

Since |χ(n)| = 1, the series will converge absolutely iff ℜ(s) > 1. For our proof, we will need to show that it converges conditionally on ℜ(s) > 0 (except for s = 1, χ = χ_{0}), and that it is nonzero at s = 1. To do this, we will first show that we can also write L(s, χ) as an infinite product. Note that since

L(s, χ) = 1 + \frac{χ(2)}{2^{s}} + \frac{χ(3)}{3^{s}} + …,

we have, for example,

\frac{χ(2)}{2^{s}}L(s, χ) = \frac{χ(2)}{2^{s}} + \frac{χ(4)}{4^{s}} + \frac{χ(6)}{6^{s}} + …

so that

(1 − \frac{χ(2)}{2^{s}}) L(s, χ) = 1 + \frac{χ(3)}{3^{s}} + \frac{χ(5)}{5^{s}} + …,

and in general

(1 − \frac{χ(p)}{p^{s}}) L(s, χ) = ∑_{n∉(p)} \frac{χ(n)}{n^{s}}.

Repeating the process for all primes gives:

∏_{p} (1 − \frac{χ(p)}{p^{s}}) L(s, χ) = 1,

so we have

L(s, χ) = ∏_{p} (1 − \frac{χ(p)}{p^{s}})^{−1} .  (6)

Lemma: For χ ≠ χ_{0}, L(s, χ) converges in the region ℜ(s) > 0. L(s, χ_{0}) converges for ℜ(s) > 0 except at s = 1, where it has a simple pole.

Proof: By (3), we know that for χ ≠ χ_{0},

∑_{n=N+1}^{N+b} χ(n) = ∑_{n̄∈(Z/bZ)^{∗}} χ(n̄) = 0,

so the partial sums of the sequence χ(n) for n = 1, 2, 3, … are bounded by the constant max_{1≤N≤b} ∑_{n=1}^{N} χ(n). Since ℜ(s) > 0, the sequence \frac{1}{n^{s}} is converging monotonically to 0, so L(s, χ) = ∑_{n=1}^{∞} \frac{χ(n)}{n^{s}} converges by Dirichlet’s Test.

For χ = χ_{0}, we have

L(s, χ_{0}) = ∏_{p} (1 − \frac{χ_{0}(p)}{p^{s}})^{−1}

= ∏_{p∤b}(1 − \frac{1}{p^{s}} )^{−1}

= ∏_{p} (1 − \frac{1}{p^{s}} )^{−1} ∏_{p|b} (1 − \frac{1}{p^{s}} )

= ζ(s) ∏_{p|b} (1 − \frac{1}{p^{s}} ) ,

where ζ(s) is the Zeta Function, which has an analytic extension to ℜ(s) > 0 except at s = 1, where it has a simple pole with residue 1.

Corollary: L(1, χ) ≠ 0.

Proof: We have already seen that L(s, χ_{0}) has a simple pole at s = 1. Let P (s) = ∏_{χ∈Ĝ} L(s, χ). P is the product of analytic functions on ℜ(s) > 0, so it is analytic, except possibly for a simple pole at s = 1. Since P is meromorphic, it is continuous on ℜ(s) > 0 (when viewed as a map C → Ĉ). Let us assume that none of the functions L(s, χ), χ ∈ Ĝ, are uniformly zero on Re(s) > 0. Then, because they are meromorphic, ∀δ > 0, ∃x ∈ R_{>1} with |x − 1| < δ such that ∀χ ∈ Ĝ, L(x, χ) ≠ 0 (because otherwise we would have an infinite sequence of zeroes with an accumulation point) For such x, P (x) ≠ 0, and we can take the log:

ln(P (x)) = ∑_{χ∈Ĝ} ln (L(x, χ))

= ∑_{χ∈Ĝ} ln (∏_{p} (1 − \frac{χ(p)}{p^{x}})^{−1})

= − ∑_{χ∈Ĝ} ∑_{p} ln (1 − \frac{χ(p)}{p^{x}})

= ∑_{χ∈Ĝ} ∑_{p} ∑_{n=1}^{∞} \frac{χ^{n}(p)}{np^{xn}}

= ∑_{p} ∑_{n=1}^{∞} \frac{1}{np^{xn}} ∑_{χ∈Ĝ} χ(p^{n}),

where we can switch the order of the sums because they are absolutely convergent for our choice of x. Note that we have used the fact that the analytic continuation of ln(1 − y) to the complex numbers is ln(1 − z) = ∑_{n=1}^{∞} \frac{z^{n}}{n} for |z| < 1. By (3), the sum is non-negative, so ln(P (x)) ≥ 0, and thus P (x) ≥ 1 for x on the positive real line arbitrarily close to 1. Now suppose that for some χ ∈ Ĝ we have L(1, χ) = 0. We know that L(s, χ_{0}) has a simple pole at 1, so χ ≠ χ_{0}, and therefore χ̄ = χ^{−1} ≠ χ. However, we still have

L(1, χ̄) = ∑_{n=1}^{∞} \frac{χ̄(n)}{n}

= \overline{∑_{n=1}^{∞} \frac{χ(n)}{n}}
= \overline{L(1, χ)}
= 0,

so there are at least two χ ∈ Ĝ for which L(1, χ) = 0. χ_{0} is the only character for which L(1, χ) is infinite, and it has only a simple pole, so the product P (s) will have at least a first-order 0 at s = 1. Since P does not have a pole at 1, it is continuous there. But we have already seen that P (s) ≥ 1 arbitrarily close to s = 1, so we have a contradiction. To prove that L(1, χ) ≠ 0, all that remains for us to show is that L(s, χ) is not uniformly zero on Re(s) > 0. But this is obvious: L(s, χ) = 1 + ∑_{n=2}^{∞} \frac{χ(n)}{n^{s}}. By choosing ℜ(s) arbitrarily large, we can make the absolute value of the infinite sum arbitrarily small. In particular, we can make it smaller than 1, so that L(s, χ) ≥ 1−|∑_{n=2}^{∞} \frac{χ(n)}{n^{s}} | > 0.

Note that since L(s, χ) is meromorphic at s = 1, the fact that it is nonzero at 1 implies that it is nonzero in a neighborhood of 1. Now that we have proved the two key properties of Dirichlet L-series, we are ready to move on to the main proof of the theorem.

4 The Proof

We will actually prove a slightly stronger version of Dirichlet’s Theorem than the one stated at the beginning of the paper. In particular, we will show that there are ”equally many” primes p ≡ a (mod b) for each a ∈ (Z/bZ)^{∗}. To make this statement more exact, we will introduce the idea of Dirichlet densities. Definition: The Dirichlet density of some subset S of the prime numbers is

lim_{s→1^{+}} (\frac{∑_{p∈S} p^{−s}}{∑_{p} p^{−s}} ) ,  (7)

assuming that this limit exists.

We will show each set S_{a} ≡ {primes p | p ≡ a (mod b)} has Dirichlet density \frac{1}{ϕ(b)}, or, equivalently, that

lim_{s→1^{+}} ( ∑_{p≡a (mod b)} \frac{1}{p^{s}} − \frac{1}{ϕ(b)} ∑_{p} \frac{1}{p^{s}} )  (8)

is finite. Assuming that the second sum diverges as s → 1, the only way the difference can be finite is if there are an infinite number of terms in the first sum, i.e., there are infinitely many primes p ≡ a (mod b).

Proposition: ∑_{p} \frac{1}{p^{s}} diverges as s → 1^{+}.

Proof: We will take s to be real. For each prime p, consider

|\frac{1}{p^{s}} + ln (1 − \frac{1}{p^{s}} )| = |\frac{1}{p^{s}} − ∑_{n=1}^{∞} \frac{1}{np^{ns}} |

= ∑_{n=2}^{∞} \frac{1}{np^{ns}}

< \frac{1}{2} ∑_{n=2}^{∞} \frac{1}{p^{ns}}

≤ \frac{1}{2} ∑_{n=2}^{∞} \frac{1}{p^{n}}
= \frac{1}{2}p^{−2} \frac{1}{1 − p^{−1}}
= \frac{1}{2p(p − 1)}
≤ \frac{1}{p^{2}} .

Since ∑_{p} \frac{1}{p^{2}} < ∑_{n=1}^{∞} \frac{1}{n^{2}} converges absolutely, it follows that lim_{s→1^{+}} ∑_{p} (\frac{1}{p^{s}} + ln (1 − \frac{1}{p^{s}} )) also converges absolutely. Now suppose that lim_{s→1^{+}} ∑_{p} \frac{1}{p^{s}} exists. Since s is real, each term is positive, so the sum conveges absolutely. Thus it follows that

lim_{s→1^{+}} ∑_{p} (\frac{1}{p^{s}} + ln (1 − \frac{1}{p^{s}} )) − lim_{s→1^{+}} ∑_{p} \frac{1}{p^{s}} = lim_{s→1^{+}} ∑_{p} ln (1 − \frac{1}{p^{s}} ) .

In particular, the limit on the right-hand side must converge to the difference of the limits on the left-hand side. The exponential of the right-hand side, lim_{s→1^{+}} ∏_{p} (1 − \frac{1}{p^{s}} ), must therefore have a finite non-zero value. But then

lim_{s→1^{+}} ζ(s) = (lim_{s→1^{+}} ∏_{p} (1 − \frac{1}{p^{s}} ))^{−1} would have a finite value. (Notice that we have pulled the limit sign out of an exponent and inside an inverse in the last two step, as we are allowed to do if the limit exists.) We know that ζ(s) has a pole at 1, so it must be that ∑_{p} \frac{1}{p^{s}} diverges as s → 1^{+}.

We will now show that the limit in (8) is finite. For s with ℜ(s) > 1, consider

∑_{χ∈Ĝ} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}} = ∑_{p} \frac{∑_{χ∈Ĝ} χ(a^{−1}p)}{p^{s}}  (9)

= ∑_{p≡a (mod b)} \frac{ϕ(b)}{p^{s}}  (10)

= ϕ(b) ∑_{p≡a (mod b)} \frac{1}{p^{s}} .  (11)

We were able to switch the order of the sums in (9) because ∑_{p} \frac{χ(p)}{p^{s}} is absolutely convergent for ℜ(s) > 1. We can rewrite the left-hand side of the equation by removing the trivial character from the sum:

∑_{χ∈Ĝ} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}} = χ_{0}(a^{−1}) ∑_{p} \frac{χ_{0}(p)}{p^{s}} + ∑_{χ≠χ_{0}} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}} (12)

= ∑_{p} \frac{1}{p^{s}} + ∑_{χ≠χ_{0}} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}}.  (13)

Combining (11) and (13), we have

ϕ(b) ∑_{p≡a (mod b)} \frac{1}{p^{s}} = ∑_{p} \frac{1}{p^{s}} + ∑_{χ≠χ_{0}} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}},

which we can rewrite as

∑_{p≡a (mod b)} \frac{1}{p^{s}} − \frac{1}{ϕ(b)} ∑_{p} \frac{1}{p^{s}} = \frac{1}{ϕ(b)} ∑_{χ≠χ_{0}} χ(a^{−1}) ∑_{p} \frac{χ(p)}{p^{s}}.  (14)

The left-hand side is the argument of the limit in (8), so we can complete our proof of Dirichlet’s Theorem by showing that the right-hand side has a finite limit as s → 1^{+}. There are a finite number of characters χ, so all we have to show is that for all χ ≠ χ_{0}, the infinite sum ∑_{p} \frac{χ(p)}{p^{s}} converges as s → 1^{+}. Proposition: ∑_{p} \frac{χ(p)}{p^{s}} converges as s → 1^{+} for all χ ≠ χ_{0}.

Proof: We will proceed by showing that the sum differs from ln(L(s, χ)) by an analytic function in a neighborhood around 1. (Since L(s, χ ≠ χ_{0}) is analytic for s > 0 and L(s, χ) ≠ 0 near 1, it follows that ln(L(s, χ)) is analytic near 1, and therefore so is its sum with any analytic function.) The proof is similar to the one showing that ∑_{p} \frac{1}{p^{s}} diverges as s → 1^{+}.

ln(L(s, χ)) − ∑_{p} \frac{χ(p)}{p^{s}} = ln (∏_{p} (1 − \frac{χ(p)}{p^{s}})^{−1}) − ∑_{p} \frac{χ(p)}{p^{s}}

= ∑_{p} (− ln (1 − \frac{χ(p)}{p^{s}}) − \frac{χ(p)}{p^{s}})

= ∑_{p} (∑_{n=1}^{∞} \frac{χ^{n}(p)}{np^{ns}} − \frac{χ(p)}{p^{s}})

= ∑_{p} ∑_{n=2}^{∞} \frac{χ^{n}(p)}{np^{ns}}.

This series is absolutely convergent in the region ℜ(s) > 1/2:

∑_{p} ∑_{n=2}^{∞} |\frac{χ^{n}(p)}{np^{ns}} | = ∑_{p} ∑_{n=2}^{∞} \frac{1}{np^{nℜ(s)}}

< \frac{1}{2} ∑_{p} ∑_{n=2}^{∞} p^{−nℜ(s)}

= \frac{1}{2} ∑_{p} p^{−2ℜ(s)} \frac{1}{1 − p^{−ℜ(s)}}

= \frac{1}{2} ∑_{p} \frac{1}{p^{ℜ(s)}(p^{ℜ(s)} − 1)}

which converges (since the terms decrease like 1/p^{2ℜ(s)}, and 2ℜ(s) > 1), completing the proof of Dirichlet’s Theorem.

5 The Chebotarev Density Theorem

The following is a generalization of Dirichlet’s Theorem: Chebotarev’s Density Theorem: Let L be a Galois extension of number field K, and for σ ∈ Gal(L/K) define C_{σ} to be the conjugacy class of σ. Let S be the set of prime ideals 𝔭 of K such that for every prime ideal 𝔓 of L lying over 𝔭, the Frobenius element of 𝔓 is in C_{σ}. Then S has Dirichlet density \frac{|C_{σ}|}{|Gal(L/K)|}.

To see how Dirichlet’s Theorem follows, let K = Q and let L = Q(ζ_{b}), where ζ_{b} is one of the primitive b^{th} roots of unity. Q(ζ_{b}) is an Abelian extension of Q with Galois group (Z/bZ)^{∗}, so C_{σ} = {σ} for all σ ∈ Gal(Q(ζ_{b})/Q), and the Frobenius element of 𝔓 is just the Artin symbol (\frac{Q(ζ_{b})/Q}{p}) = p̄ ∈ (Z/bZ)^{∗} for all 𝔓 lying over any prime p that does not divide b. Thus we see that there is a bijective correspondence between the conjugacy classes mod b of primes that do not divide b and the elements of the Galois group, so that the set S in the statement of the theorem becomes S_{a} = {primes p ∈ Z | p ≡ a (mod b)}. Since |C_{σ}| = 1 and |Gal(Q(ζ_{b})/Q)| = ϕ(b), the theorem tells us that the set S_{a} has density \frac{1}{ϕ(b)} for each a ∈ (Z/bZ)^{∗}, which is exactly what we showed in proving Dirichlet’s Theorem.

6 Computation

The form of Dirichlet’s Theorem that we have proved tells us that, on average, one of every ϕ(b) primes will be congruent to a (mod b). It is possible, however, that for a given a, b, the distribution of primes will be very uneven; the theorem does not guarantee that, say, one of the first ϕ(b) primes that do not divide b will be congruent to a. We can, however, find experimentally how long it takes to find a prime p ≡ a (mod b) for various a, b. The following MAGMA code will find the first prime p = a + nb for 0 ≤ n ≤ c, or return −1 if there is no such prime, i.e., if our choice of c is too small. (It will return 0 if we have entered inappropriate values for a, b, or c.)

findp:=function(a,b,c)
if not (IsIntegral(a) and IsIntegral(b) and IsIntegral(c)) then
return 0;
end if;
if ((a le 0) or (c le 0) or (b le 1)) then
return 0;
end if;
if Gcd(a,b) ne 1 then
return 0;
end if;
if Gcd(a,b) eq 1 then
x:=-1;
for n in [0..c] do
if IsPrime(a+n*b) then
x:=n;
return [n,a+n*b];
end if;
end for;
return x;
end if;
end function;

Using this function, one can then easily write a double for-loop to check a desired range of values for a and b. (In doing this, one may wish to change the function so that it will return a and b along with n and a + nb.) For a, b ≤ 20, we find that there is always a prime p = a + nb with n ≤ 10, and the only choice for which we have to go out to n = 10 is a = 1, b = 19. For b = 100, the largest value of n for any a is 4. For b = 97 (a prime), the highest n is 15. If we set a = 1 and let b range over the integers less than 100, the highest n is 12. For 100 ≤ b ≤ 110, 30 ≤ a ≤ 40 (to choose an arbitrary range of values), the largest value of n is 14. From these examples, it seems that n will generally not be larger ϕ(b), from which we can guess that the primes p ≡ a (mod b) are fairly evenly distributed.