From antiquity, Euclid’s Theorem asserts that the number of primes is infinite. Since all primes except are odd, a re-phrasement of Euclid’s theorem is that the set of odd integers contains an infinite number of primes. A natural generalization, proved by Dirichlet, is that every arithmetic progression of the form contains an infinite number of primes, provided that and are relatively prime.

The proof is one of the first application of Fourier analysis on finite abelian groups. Here in this post, we prove Dirichlet’s theorem when , i.e., both the arithmetic progressions and contain an infinite number of primes. The restriction to highlights the main structure of Dirichlet’s proof without needing as much background from number theory.

Before jumping directly into the proof, let us first discuss some number-theoretic background and the high-level strategy. First recall Euclid’s argument. For the sake of contradiction, there are exactly primes of the . Then the number is larger than every and cannot be a prime of the form . On the other hand, from the Fundamental Theorem of Arithmetic, is the product of primes, and one of them must be congruent to since itself is. So some must divide both and and , implying that divides , a contradiction. One can easily verify that this argument can be adapted to by taking . However, the argument breaks down when applied to the arithmetic progression . The reason is that the number is no longer guaranteed to have a prime divisor of the form .

Instead, Euler’s analytic proof of Euclid’s Theorem provides the proper framework to extend the infinitude of primes to arithmetic progressions, where the zeta function can be written as the product of geometric series of primes:

(A note on notation: always denotes a prime, and and range over all primes.) The identity can be viewed as an analytic version of the Fundamental Theorem of Arithmetic: every positive integer is the product of some prime powers, and the expression is a geometric series. Since diverges, The Product Formula also implies that the number of primes is infinite. With additional calculation, Euler proved the stronger form of Euclid’s Theorem:

Now to prove Dirichlet’s Theorem, we will show that the sum as , where is the indicator function on for being congruent to . By Fourier analysis, can be decomposed into two sums. Roughly, the first corresponds to the zeroth Fourier coefficient of and evaluates to , which diverges as , and the second sum corresponds to the non-zero Fourier coefficients and is always bounded. In our writeup, the advantage of restricting to is that the estimate of the second sum becomes significantly simpler, without further tools from number theory.

for every ,

where ranges over all characters of the dual group of . Since is a finite abelian group, it is is also isomorphic to its dual, and with , we can conclude that the only characters of are: the trivial character that is identically , and the character where if

and if . Thus, we can simplify and rewrite as

(For sanity check, one can easily verify via direct computation, without Fourier analysis, that the identities and hold.) For the rest of this proof, we will rely on the the fact that the characters and are real-valued.

To prove the theorem, we have to sum over all integers instead of just the multiplicative subgroup of . To this end, for every character , we define its *Dirichlet character* to be the extension to all of as follows: if and otherwise. Let be the indicator function of being congruent to . Then it is easy to see that

where are the Dirichlet characters of , respectively. Since we can express the indicator function in terms of Dirichlet characters, we have

It suffices to prove that as . In particular, we will show that

- as , which coincides with Euler’s argument since for all , and
- .

To estimate these sums, we prove the following:

Since is real-valued, taking log of both sides, we have

where the second line follows from the estimate of the power series when , and the third from the fact that converges.

Now we estimate the two sums using the above proposition. For the trivial Dirichlet character , we have

which diverges as since diverges as .

For the non-trivial character , is simply the alternating series , which converges to a positive number. Thus,

completing the proof.

We finish by observing that the proof above has a quantitative form.

with and . Previously, we simply noted that diverges as . To finish the proof, it suffices to note that