DIRICHLET’S THEOREM ON PRIMES IN ARITHMETIC PROGRESSIONS

INNA ZAKHAREVICH

1. Introduction

It is a well-known fact that there are infinitely many primes. However, it is less clear how the primes are distributed throughout the integers. A natural question to ask is whether there are infinitely many primes in arithmetic progressions: sequences of the form a, a + q, a + 2q, a + 3q, . . .. Clearly, there will be none in some sequences. If a = 4 and q = 8 then all elements of the sequence will be divisible by 4, so there clearly can’t be any primes. In other progressions it is less clear. If a = 5 and q = 7, then there are many primes: the first 7 elements of the sequence are 5, 12, 19, 26, 33, 40, 47, which already contains 3 primes. It turns out that if no number other than 1 divides all elements of the sequence, there will be infinitely many primes in the sequence. More formally,

Theorem 1. If a, q are positive integers with (a, q) = 1, then there are infinitely many primes in the sequence {a + np}_{n∈} .

We seek to prove this theorem. To do so, we first introduce two objects, the Dirichlet series A(s, f) and the Dirichlet character χ_{q}, and prove some useful results about them. We will then use these to show that

lim_{s→1} ∑_{p≡a (mod q)} \frac{1}{p^{s}} = ∞

which will show that there must be infinitely many primes in the sum on the left.

We assume some basic knowledge of number theory (the properties of the group of units modulo n) and complex analysis (some familiarity with analytic functions).

2. Dirichlet Series

Definition 2. A Dirichlet series is a sum of the form

(1)  A(s, f) = ∑_{n=1}^{∞} \frac{f(n)}{n^{s}},

The Riemann-Zeta Function, ζ(s), is the Dirichlet series where f(n) = 1 for all n.

The question of convergence for Dirichlet series is a complicated one. However, if we restrict our attention to absolute convergence, we can quickly obtain a useful result:

Theorem 3. For each Dirichlet series A(s, f) = ∑_{n=1}^{∞} f(n)/n^{s} there exists a unique number σ_{f} ∈ ∪ {±∞} such that the series A(s, f) is absolutely convergent for Re s > σ_{f}, and not for Re s < σ_{f}.

Proof. We follow the proof in [1].

Let S be the set of all α such that

∑_{n=1}^{∞} |f(n)|n^{−α} < ∞.

Since |n^{−s}| = n^{−Re s} is a monotonically decreasing function of Re s, we know from the comparison test that the series ∑_{n=1}^{∞} f(n)n^{−s} is absolutely convergent for Re s > α; thus if α ∈ S then all β > α are in S. Let σ_{f} = inf S. Then by the definition of σ_{f}, we know that there does not exist s with Re s < σ_{f} such that ∑_{n=1}^{∞} f(n)n^{−s} is absolutely convergent.

So we have shown that if S is nonempty we are done. If S is empty, set σ_{f} = ∞, and the theorem will hold for σ_{f}. □

Notice that if we apply the integral test to the series for ζ(s), we get that σ_{f} = 1.

If we make some extra assumptions on f we can obtain a useful factorization of the series, known as the Euler product. The existence of such a factorization hints at the connection between these series and theorems about primes; it is often useful to take the logarithm of such a product to obtain facts about sums over primes.

Proposition 4. If A(s, f) = ∑_{n=1}^{∞} f(n)n^{−s} and f(nm) = f(n)f(m) for all n, m then we have

(2)  A(s, f) = ∏_{p} (1 − \frac{f(p)}{p^{s}})^{−1}

for all s such that Re s > σ_{f}.

Proof. Notice that for Re s > σ_{f}

∑_{k=0}^{∞} \frac{|f(p^{k})|}{|p^{sk}|} ≤ ∑_{n=1}^{∞} \frac{|f(n)|}{|n^{s}|},

so the series on the left converges, and thus equals (1 − f(p)/p^{s})^{−1}. Also, notice that for the first N primes p_{1}, …, p_{N}, we have

∑_{n=1}^{∞} \frac{f(n)}{n^{s}} − ∏_{m=1}^{N} (1 − \frac{f(p_{m})}{p_{m}^{s}})^{−1} = ∑_{n=1}^{∞} \frac{f(n)}{n^{s}} − ∑_{e_{1},...,e_{N}} \frac{f(p_{1}^{e_{1}} ⋯ p_{N}^{e_{N}})}{p_{1}^{e_{1}s} ⋯ p_{N}^{e_{N}}}
≤ ∑_{n=p_{N} +1}^{∞} \frac{f(n)}{n^{s}}

which can be made arbitrarily small since A(s, f) exists. Thus the two formulas converge to the same value, and we are done. □

The Riemann Zeta function is the most famous Dirichlet series. It is useful in proving theorems about the distributions of primes. Here we prove a simple bound on ζ(s):

Proposition 5. For real s > 1,

ζ(s) = \frac{1}{s − 1} + O(1)

uniformly.

Proof. Notice that (n + 1)^{−s} ≤ ∫_{n}^{n+1} u^{−s} du ≤ n^{−s} for n ∈ . Summing over n we see that ζ(s) − 1 ≤ ∫_{1}^{∞} u^{−s} du ≤ ζ(s) for s > 1. Computing the integral and rearranging the inequality, we find that

\frac{1}{s − 1} ≤ ζ(s) ≤ \frac{1}{s − 1} + 1

for s > 1. Thus

ζ(s) = \frac{1}{s − 1} + O(1).

□

3. Dirichlet Characters

Definition 6. A Dirichlet character is a function χ_{q} : → such that (1) if n ≡ m (mod q) then χ_{q}(m) = χ_{q}(n),

(2) χ_{q}(mn) = χ_{q}(m)χ_{q}(n) for all m, n ∈ , and

(3) χ_{q}(n) = 0 if and only if (n, q) ≠ 1.

Although the definition of Dirichlet characters does not seem restrictive, it turns out that it is very simple to classify all Dirichlet characters. First, in order to simplify our exposition, we introduce some notation:

Definition 7. We denote the cardinality of of ( /n )^{∗} by φ(n). For any integer a such that (a, n) = 1 we denote the smallest integer k such that a^{k} ≡ 1 (mod n) by ord_{n}(a).

Definition 8. We denote the complex number exp(2π/a), a primitive a-th root of unity, by ζ_{a}.

Proposition 9. There are exactly φ(q) distinct χ_{q}. If b_{1}, …, b_{m} are the generators of ( /q )^{∗} then the χ_{q} are exactly the functions defined by

χ_{q}(a) = ζ_{ord_{q}(b_{1})}^{k_{1}e_{1}} ⋯ ζ_{ord_{q}(b_{m})}^{k_{m}e_{m}}

where 0 ≤ k_{j} < ord_{q}(b_{j}) if a ≡ b_{1}^{e_{1}} ⋯ b_{m}^{e_{m}} (mod q) and χ_{q}(a) = 0 otherwise.

We will denote the character where k_{j} = 0 for all j = 1, …, m by ϵ_{q}.

Proof. Plugging n = m = 1 into property 2 we see that χ_{q}(1 · 1) = χ_{q}(1)^{2} so χ_{q}(1) = 0 or 1. Since it can’t equal 0 by property 3, χ_{q}(1) = 1. Suppose that (a, q) = 1. Then a^{φ(q)} ≡ 1 (mod q), so χ_{q}(a)^{φ(q)} = χ_{q}(1) = 1, so χ_{q}(a) must be a φ(q)-th root of 1.

Notice that since χ_{q}(b_{j}^{ord_{q}(b_{j})}) = 1, we know that χ_{q}(b_{j}) = ζ_{ord_{q}(b_{j})}^{k_{j}} for some 0 ≤ k_{j} < ord_{q}(b_{j}). Thus all χ_{q} must be of the desired form. Now fix k_{j} for each b_{j}, and define χ_{q} on the rest of ( /q )^{∗} by χ_{q}(b_{1}^{e_{1}} ⋯ b_{m}^{e_{m}}) = χ_{q}(b_{1})^{k_{1}e_{1}} ⋯ χ_{q}(b_{m})^{k_{m}e_{m}}. Define χ_{q}(a) = 0 if (a, q) ≠ 1. Then by definition this function will satisfy the definition of a Dirichlet character. Thus all Dirichlet characters satisfy the given formulas.

Notice that from the formula we see that there are ∏_{k=1}^{m} ord_{q}(b_{j}) different Dirichlet characters. But ∏_{j=1}^{m} ord_{q}(b_{j}) = #( /q )^{∗} = φ(q) by definition. □

Theorem 10. For (a, q) = 1,

∑_{χ_{q}} χ_{q}(a)^{−1}χ_{q}(p) = \{ \begin{matrix}φ(q) & if a ≡ p (mod q) \\ 0 & otherwise. \end{matrix}

Proof. Let b_{1}, …, b_{m} be generators of ( /q )^{∗}. If (p, q) ≠ 1 then the theorem is trivially true. So now suppose that (p, q) = 1. Let a = ∏_{j=1}^{m} b_{j}^{e_{j}} and let p = ∏_{j=1}^{m} b_{j}^{f_{j}}. Then

∑_{χ_{q}} χ_{q}(a)^{−1}χ_{q}(p) = ∑_{χ_{q}} (∏_{j=1}^{m} χ_{q}(b_{j})^{−e_{j}}) (∏_{j=1}^{m} χ_{q}(b_{j})^{f_{j}})

= ∑_{χ_{q}} ∏_{j=1}^{m} χ_{q}(b_{j})^{f_{j}−e_{j}}

If f_{j} = e_{j} (so p ≡ a (mod q)) this is just ∑_{χ_{q}} 1 = φ(q). Otherwise, suppose that m′ is the largest index such that f_{m′} ≠ e_{m′}. Then if we let C = ∏_{j=m′+1}^{m} ord_{q}(b_{j}) then

∑_{χ_{q}} ∏_{j=1}^{m} χ_{q}(b_{j})^{f_{j}−e_{j}} = C ∑_{k_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{k_{m′}=1}^{ord_{q}(b_{m′})} ∏_{j=1}^{m′} ζ_{ord_{q}(b_{j})}^{k_{j}(f_{j}−e_{j})}

= C ∑_{k_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{k_{m′−1}=1}^{ord_{q}(b_{m′−1})} ∏_{j=1}^{m′−1} ζ_{ord_{q}(b_{j})}^{k_{j}(f_{j}−e_{j})} ∑_{k_{m′}=1}^{ord_{q}(b_{m′})} ζ_{ord_{q}(b_{m′})}^{k_{m′}(f_{m′}−e_{m′})}

= C ∑_{k_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{k_{m′−1}=1}^{ord_{q}(b_{m′−1})} ∏_{j=1}^{m′−1} ζ_{ord_{q}(b_{j})}^{k_{j}(f_{j}−e_{j})} \frac{1 − ζ_{ord_{q}(b_{m′})}^{(f_{m′}−e_{m′})ord_{q}(b_{m′})}}{1 − ζ_{ord_{q}(b_{m′})}^{f_{m′}−e_{m′}}}
= 0

because ζ_{ord_{q}(b_{m′})}^{(f_{m′}−e_{m′})ord_{q}(b_{m′})} = 1. So we are done. □

4. Proof of the Main Theorem

Theorem 10 tells us that we can pick out one equivalence class modulo q in a sum of Dirichlet series by summing over A(s, χ_{q}) with the correct coefficients. More specifically, we will take the logarithm of the Euler product decompositions of A(s, χ_{q}) and take a linear sum of those. Since the sums in the logarithms will be over primes p, we will be able to make a sum that is over only primes that are equivalent to a fixed a modulo q. All that will remain will be to show that those sums are infinite.

Notice that by comparison with ζ, we see that σ_{f} for A(s, χ_{q}) is at most 1. We show the connection between log A(s, χ_{q}) and an infinite sum over primes:

Theorem 11. Let χ_{q} be a Dirichlet character. Then for real s > 1,

∑_{p} ∑_{k=1}^{∞} \frac{1}{k}χ_{q}(p)^{k}p^{−ks} = log A(s, χ_{q}).

Proof. We follow the proof in [1].

Take logarithms of both sides of (2). Then we find that

log A(s, χ_{q}) = ∑_{p} log(1 − χ_{q}(p)p^{−s})^{−1}.

Since |χ_{q}(p)p^{−s}| < 1, we can use the power series expansion for log(1 − z)^{−1} to get that

log A(s, χ_{q}) = ∑_{p} ∑_{k=1}^{∞} \frac{1}{k}χ_{q}(p)^{k}p^{−ks}.

□

(As in [1]) So we now have an infinite sum over prime powers. To reduce this to a sum over primes, we note that for s ≥ 1

∑_{p} ∑_{k=2}^{∞} \frac{1}{k}p^{−ks} ≤ ∑_{p} ∑_{k=2}^{∞} p^{−ks} = ∑_{p} \frac{p^{−2s}}{1 − p^{−s}} ≤ ∑_{p} \frac{1}{p(p − 1)}

which converges by comparison with 1/n^{2}. Thus from the above we see that

∑_{p} \frac{χ_{q}(p)}{p^{s}} = log A(s, χ_{q}) + O(1).

Then for integers a, q such that (a, q) = 1 and s > 1 (3)

\frac{1}{φ(q)} ∑_{χ_{q}} χ_{q}(a)^{−1} log A(s, χ_{q}) = \frac{1}{φ(q)} ∑_{p} ∑_{χ_{q}} \frac{χ_{q}(p)χ_{q}(a)^{−1}}{p^{s}} + O(1) = ∑_{p≡a (mod q)} \frac{1}{p^{s}} + O(1).

So we have now written a sum over primes equivalent to a modulo q. It remains to give an estimate of this sum.

First, we give an asymptotic for A(s, ϵ_{q}), which has a pole at s = 1:

Proposition 12.

A(s, ϵ_{q}) = \frac{1}{s − 1} + O(q).

Proof. Notice that for s > 1

A(s, ϵ_{q}) = ζ(s) − ∏_{p|q}(1 − p^{−s})^{−1}.

So if we could show that ∏_{p|q}(1 − p^{−s})^{−1} is O(q), we would be done. Indeed,

∏_{p|q}(1 − p^{−s})^{−1} ≤ ∏_{p|q}(1 − 2^{−s})^{−1} ≤ ∏_{p|q} 2 ≤ q = O(q).

So we are done. □

Now we can estimate the Dirichlet series for the other characters.

Proposition 13. If χ_{q} is a Dirichlet character not equal to ϵ_{q}, then A(s, χ_{q}) is a continuous function whenever Re s > 0.

Proof. We follow [3]. Let S(x) = ∑_{n≤x} χ_{q}(n).

Notice that if χ_{q} is a Dirichlet character not equal to ϵ_{q}, we know that

∑_{k=ℓ}^{ℓ+q} χ_{q}(k) = ∑_{k=1}^{q} χ_{q}(k) = ∑_{e_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{e_{m}=1}^{ord_{q}(b_{m})} χ_{q}(b_{1}^{e_{1}} ⋯ b_{m}^{e_{m}})

= ∑_{e_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{e_{m−1}=1}^{ord_{q}(b_{m−1})} χ_{q}(b_{1}^{e_{1}} ⋯ b_{m−1}^{e_{m−1}}) ∑_{e_{m}=1}^{ord_{q}(b_{m})} χ_{q}(b_{m}^{e_{m}})

= ∑_{e_{1}=1}^{ord_{q}(b_{1})} ⋯ ∑_{e_{m−1}=1}^{ord_{q}(b_{m−1})} χ_{q}(b_{1}^{e_{1}} ⋯ b_{m−1}^{e_{m−1}})\frac{1 − χ_{q}(b_{m})^{ord_{q}(b_{m})}}{1 − χ_{q}(b_{m})} = 0.

so |S(x)| is uniformly bounded by max_{1≤k<q} |∑_{j=1}^{k} χ_{q}(j)|.

Now observe that

A(s, χ_{q}) = ∑_{n=1}^{∞} S(n) (\frac{1}{n^{s}} − \frac{1}{(n + 1)^{s}} )
= s ∑_{n=1}^{∞} S(n) ∫_{n}^{n+1} x^{−s−1} dx = s ∫_{1}^{∞} S(x)x^{−s−1}.

Since S(x) is uniformly bounded the above integral is analytic and converges for all s with Re s > 0, so A(s, χ_{q}) is an analytic function on the half-plane Re s > 0. □

In particular, this means that A(s, χ_{q}) tends to a finite limit as s → 1. If we could show that A(1, χ_{q}) ≠ 0 then log A(1, χ_{q}) would be finite, and by considering (3) we would know that

∑_{p≡a (mod q)} \frac{1}{p^{s}} = \frac{1}{φ(q)} log \frac{1}{s − 1} + O(log q).

This tends to infinity as s → 1, so there must be infinitely many primes in the left-hand sum. This is Dirichlet’s theorem:

Theorem 14. If a, q are positive integers such that (a, q) = 1 then there are infinitely many primes in the sequence {a + kq}_{k∈} .

We finish the proof by showing the following:

Theorem 15. If χ_{q} is a Dirichlet character not equal to ϵ_{q}, then A(1, χ_{q}) ≠ 0.

Proof. We follow [3].

First we will prove a lemma:

Lemma 15.1. For real s > 0,

∏_{χ_{q}} A(s, χ_{q}) ≥ 1.

Proof. Recall that

log A(s, χ_{q}) = ∑_{p} ∑_{k=1}^{∞} \frac{1}{k}χ_{q}(p^{k})p^{−ks}.

Summing over χ_{q} and using theorem 10 we see that

∑_{χ_{q}} log A(s, χ_{q}) = ∑_{p} ∑_{k=1}^{∞} \frac{1}{k} (∑_{χ_{q}} χ_{q}(p^{k})) p^{−ks} = φ(q) ∑_{p^{k}≡1 (mod m)}^{∞} \frac{1}{k}p^{−ks}.

For real s the right-hand side is nonnegative. Thus

∏_{χ_{q}} A(s, χ_{q}) ≥ 1.

□

Now suppose that χ_{q} is a complex character (so there exists some n ∈ such that χ_{q}(n) ∉ ). From the definition of A(s, χ_{q}) we see that \overline{A(s, χ_{q})} = A(\overline{s}, \overline{χ}_{q}). Thus if A(1, χ_{q}) = 0 then A(1, \overline{χ}_{q}) = 0. In proposition 12 we saw that A(s, ϵ_{q}) had a simple pole at s = 1; A(s, χ) is analytic in the right half-plane for χ ≠ ϵ_{q}. Thus if A(1, χ_{q}) has a zero at s = 1 so does A(1, \overline{χ}_{q}), and so it will have a double zero but only a single pole at s = 1, so the product will also be zero. However, from lemma 15.1 we saw that the product is at least 1: contradiction. So for all complex characters χ_{q}, A(1, χ_{q}) ≠ 0.

So now we simply need to prove the statement for real χ_{q}, meaning χ_{q}(n) = ±1 for all n relatively prime to q. To facilitate this, we follow the exposition of a proof due to de la Vallée Poussin in [3] and prove the following lemma:

Lemma 15.2. Suppose f is a nonnegative function on such that if (m, n) = 1 then f(mn) = f(m)f(n). Suppose also that there is a constant c such that f(p^{k}) < c for all prime powers p^{k}. Then ∑_{n=1}^{∞} f(n)n^{−s} converges for all real s > 1, and

∑_{n=1}^{∞} \frac{f(n)}{n^{s}} = ∏_{p} (1 + ∑_{k=1}^{∞} \frac{f(p^{k})}{p^{ks}}) .

Proof. Fix s > 1, and let a(p) = ∑_{k=1}^{∞} f(p^{k})p^{−ks}. Then

a(p) < c ∑_{k=1}^{∞} \frac{1}{p^{ks}} = \frac{cp^{−s}}{1 − p^{−s}} < 2cp^{−s}.

Thus, using the fact that 1 + x < e^{x} for x > 0 we have

∏_{p≤N}(1 + a(p)) < ∏_{p≤N} e^{a(p)} = exp ∑_{p≤N} a(p).

But we know that ∑_{p≤N} a(p) < 2c ∑_{p} p^{−s} = M. But from the multiplicativity of f we see that

∑_{n=1}^{N} f(n)n^{−s} < ∏_{p≤N}(1 + a(p)) < exp M

for all N. Since f is nonnegative, we see that ∑_{n=1}^{∞} f(n)n^{−s} converges.

The last part follows from applying the same reasoning as in proposition 4 to this function.

□

Now suppose that χ_{q} is a real character and that A(1, χ_{q}) = 0. Consider

ψ(s) = \frac{A(s, χ_{q})A(s, ϵ_{q})}{A(2s, ϵ_{q})}.

The zero of A(s, χ_{q}) cancels out the pole of A(s, ϵ_{q}), so the numerator is analytic for Re s > 0. The denominator is analytic for Re s > 1/2, so ψ is analytic for Re s > 1/2. The denominator has a pole at s = 1/2, so as s → 1/2, ψ(s) → 0.

Suppose that s is real and s > 1/2. Then

ψ(s) = ∏_{p}(1 − χ_{q}(p)p^{−s})^{−1}(1 − ϵ_{q}(p)p^{−s})^{−1}(1 − ϵ_{q}(p)p^{−2s}) = ∏_{p |̸q} \frac{(1 − p^{−2s})}{(1 − p^{−s})(1 − χ_{q}(p)p^{−s})}.

Notice, however, that if χ_{q}(p) = −1 then this is equal to 1. So we can reduce this to

ψ(s) = ∏_{χ_{q}(p)=1} \frac{1 + p^{−s}}{1 − p^{−s}} = ∏_{χ_{q}(p)=1}(1 + p^{−s}) ∑_{k=0}^{∞} p^{−ks} = ∏_{χ_{q}(p)=1} (1 + ∑_{k=1}^{∞} 2p^{−ks}) .

Applying lemma 15.2, we see that ψ(s) = ∑_{n=1}^{∞} a_{n}n^{−s} where a_{n} ≥ 0, the series converges for s > 1, and a_{1} = 1.

Now expand ψ as a power series in s about s = 2. We know that it is analytic for Re s > 1/2, so the radius of convergence is at least 3/2. The n-th coefficient will be equal to ψ^{(n)}(2)/n!, and

ψ^{(n)}(2) = ∑_{m=1}^{∞} a_{m}(− log m)^{n}m^{−2} = (−1)^{n}c_{n},

with c_{n} ≥ 0 and c_{0} = ψ(2) = ∑_{n=1}^{∞} a_{n}n^{−2} ≥ a_{1} = 1. Thus we can write

ψ(s) = ∑_{n=1}^{∞} c_{n}(2 − s)^{n} ≥ c_{0} = 1 1/2 < s < 2.

However, this contradicts the fact that ψ(s) → 0 as s → 1/2. So A(1, χ_{q}) ≠ 0. □

5. Conclusion

We have now proven theorem 1. It is possible to prove something stronger: that, on average, there is the same number of primes in the sequences {a_{1} + kq} and {a_{2} + kq}, assuming that (a_{1}, q) = (a_{2}, q) = 1. This means that the primes are equidistributed modulo q. For an exposition of this fact, as well as a more detailed and algebraic exposition of the proof of this theorem, see [2].

References

[1] Niven, I., Zuckerman, H. S., Montgomery, H. L. An Introduction to the Theory of Numbers. New York: John Wiley & Sons, Inc., 5th ed. 1991.

[2] Fröhlich, A., Taylor, M. J. Algebraic Number Theory. Cambridge: Cambridge University Press, 1991.

[3] Ireland, Kenneth. Rosen, Michael. A Classical Introduction to Modern Number Theory. New York: Springer-Verlag, 1991. 2nd ed.