Number Theory • Topic 29

Dirichlet's Theorem

Dirichlet's Theorem on Arithmetic Progressions generalizes Euclid's proof of the infinitude of primes.

Statement

Theorem (Dirichlet's Theorem)

For any two positive coprime integers

a

and

d

(i.e.,

g cd (a, d) = 1

), there are infinitely many primes of the form:

a, a + d, a + 2 d, a + 3 d, \dots

(Primes congruent to

a (mod d)

Not only are there infinitely many, but the primes are roughly "evenly distributed" among the

ϕ (d)

possible residue classes modulo

d

. For example, primes modulo 4 are split 50-50 between

4 k + 1

and

4 k + 3

$4 k + 3$ : Use $N = 4 p_{1} \dots p_{n} - 1$ .
$4 k + 1$ : Requires quadratic residues ( $N = (2 p_{1} \dots p_{n})^{2} + 1$ ).
General case requires complex analysis (L-functions).

Exercise (Problem 1)

Show that there are infinitely many primes ending in 999.

Exercise (Problem 2)

Prove that for any

n

, the sequence of primes contains an arithmetic progression of length

n

(Green-Tao Theorem - Advanced).

Exercise (Problem 3)

Why does Dirichlet's Theorem fail if

g cd (a, d) > 1