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