|Moor Xu on 2013 Pi Day|
|peterthedestroyer on 2013 Pi Day|
|Against the “R… on Contest Math|
|The Ram on Putnam vs USAMO|
|pi on Analysis of the 24 Game|
- 48,064 hits
We will prove Dirichlet’s Theorem on Primes in Arithmetic Progressions.
Euclid proved that there are infinitely many primes. This, however, says nothing about the distribution of those primes. Dirichlet proved a stronger statement: there are infinitely many primes in every arithmetic progression; in this sense, the primes are “uniformly distributed”.
Theorem 1 (Dirichlet’s Theorem) If , then there are infinitely many primes satisfying .
Many ideas of the proof of Dirichlet’s Theorem were first seen in Euler’s proof of the infinitude of primes. Here, Euler actually showed that diverges, and that is the approach that we will take for Dirichlet’s Theorem.
1. Euler’s Proof of the Infinitude of Primes
Proposition 2 There are infinitely many primes.
Define the Riemann zeta function as
We begin with a lemma in the flavor of what we will consider in our proof.
Proof: We can approximate this sum by integrals:
From the Taylor expansion of , we see that . This allows us to write
Using , this means that
converges, we have actually proven
Combining this with Lemma 3 shows the corollary
As , the right hand side diverges, so diverges and hence there are an infinite number of primes.
2. Sketch of Proof of Dirichlet’s Theorem
We first sketch Dirichlet’s Theorem in a special case to illustrate and motivate the proof of the general theorem. Therefore, we will prove
Proposition 6 There are infinitely many primes and .
This proof will be in the same spirit as Euler’s proof of the infinitude of primes. However, since we are splitting the primes into two groups ( and ), we will need to construct a generalization of the zeta function. This generalization is the Dirichlet -function.
Definition 7 Define
This is an example of a Dirichlet character. Note that it is multiplicative () and periodic ().
Definition 8 A Dirichlet -function is then
Since we also know from Lemma 4 that
we get the expressions
Now, let , and consider
As , we already know that . We want to show that does not go to , or equivalently, that does not go to zero. In fact, goes to , which in this case is actually
Therefore, we see that is constant and hence the right hand side of
diverges as , showing that diverges and hence that there are an infinite number of primes congruent to . By precisely the same argument, there are also an infinitely number of primes congruent to .
Here, we used the character to produce the -function , and we used this -function together with the zeta function to pick out the arithmetic progression . This yielded a formula for in terms of a linear combination of and . We then showed that as , converges to something nice, which means that it doesn’t contribute much to the sum. Therefore, dominates, forcing to diverge, giving us our result.
To generalize this to arbitrary arithmetic progressions, we will need to find additional characters and show how to pick out any arithmetic progression. We will also need to show that behaves nicely under the limit and that .