A first look at Dirichlet’s theorem

As a result of Euclid’s proof that there are infinitely many prime numbers (dated back to the time around 300 BC), we know that there are infinitely many prime numbers dispersed among the odd integers 1, 3, 5, 7, 9, \cdots. It turns out that when you divide the odd integers into 2 halves (see the following two sequences), each half also contains infinitely many prime numbers:

    1, 5, 9, 13, 17, 21, 25 \cdots

    3, 7, 11, 15, 19, 23, 27 \cdots

So does each of the following sequences:

    5, 11, 17, 23, 29, 35, 41 \cdots

    7, 37, 67, 97, 127, 157, 187 \cdots

These examples provides a first look at the Dirichlet’s theorem on arithmetic progressions.
___________________________________________________________________________________________________________________

The Dirichlet’s Theorem on Arithmetic Progressions

An arithmetic progression is a sequence of numbers where each term is obtained by adding a constant to the previous term. The constant is called the common difference. If the first term is a and the common difference is d>0, the following is an arithmetic progression:

    \displaystyle a, a+d, a+2d, a+3d, \cdots

The Dirichlet’s theorem states that an arithmetic progression contains infinitely many prime numbers if the first term a and the common difference d are relatively prime (i.e. the only common divisor of a and d is 1).

The above 4 sequences of integers are all arithmetic progressions where the first term and the common difference are relatively prime. Take the third example 5, 11, 17, 23, 29, 35, 41 \cdots. The common difference is 6 and the first term is 5, which are relatively prime. By the Dirichlet’s theorem, we can be confident that this sequence contains infinitely many prime numbers. Note that not all the terms are prime (e.g. 35). So the prime numbers in an arithmetic progression do not need to be consecutive. In fact, even if an arithmetic progression contains infinitely many primes, there will always be infinitely many terms that are not prime.

Note that in the third example, the first 5 terms are primes (5, 11, 17, 23, 29) but the sixth term is not a prime. Thus 5, 11, 17, 23, 29 is a finite arithmetic progression of length 5 consisting entirely of primes. The first 6 terms 7, 37, 67, 97, 127, 157 in the fourth example is an arithmetic progression of length 6 consisting of entirely of primes.

It is a well known recent result that the prime numbers contains finite arithmetic progressions of any length. This result is known as the Green-Tao theorem and was proved by Ben Green and Terence Tao in 2004.

For a more detailed discussion of the Dirichlet’s theorem, see the Wikipedia entry on Dirichlet’s theorem on arithmetic progressions.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Another Proof of the Infinitude of Primes

In this post, we present an alternative proof that there are infinitely many prime numbers in addition to the basic proof presented in the previous post Euclid’s Proof of the Infinitude of Primes. Historically, this alternative proof is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). It is an elegant proof that is worthy to be considered as straight from “The Book” by Paul Erdos (at least “The Approximate Book”). Specifically it is one of the six proofs for the infinitude of primes found in [1].

This proof of infinitude of primes uses the notion of Fermat numbers. We present the proof in two parts.

For a proof of the infinitude of primes using topology, see The Infinitude of Primes – a Topological Proof.

___________________________________________________________________________________________________________________

Part 1

Theorem 1. There exist infinitely many positive integers F_0,F_1,F_2,F_3,\cdots such that for every i and j with i<j, the integers F_i and F_j are relatively prime (i.e. if m divides both F_i and F_j, then m=1).

The existence of F_0,F_1,F_2,F_3,\cdots implies that there are infinitely many primes. Each F_i has at least one prime factor. Then choose the smallest prime factor p_i for F_i. It is clear that p_i \ne p_j for i<j (otherwise F_i and F_j would not be relatively prime).

___________________________________________________________________________________________________________________

Part 2

One way to get the integers F_0,F_1,F_2,F_3,\cdots in Theorem 1 is through the Fermat numbers.

A positive integer is a Fermat number if it is of the form F_n=2^{2^n}+1 for some non-negative integer n. The following two points establish Theorem 1.

  1. Each Fermat number can be generated recursively by multiplying all Fermat numbers before it and then add 2. We have the following:
  2. \text{ }

      \displaystyle \biggl(\prod_{k=0}^{n-1} F_k \biggr) +2=F_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

  3. Each pair of Fermat numbers are relatively prime.

\text{ }

We can prove the above recursive relation by induction. Clearly F_0+2=F_1 (the case for n=1). Suppose that the recursive relation (1) holds for n-1 where n>1. Thus we have \displaystyle \biggl(\prod_{k=0}^{n-2} F_k \biggr) +2=F_{n-1} or \displaystyle \biggl(\prod_{k=0}^{n-2} F_k \biggr) =F_{n-1}-2. The following derives the recursive relation (1) for the general case n where n>1:

    \displaystyle \begin{aligned} \biggl(\prod_{k=0}^{n-1} F_k \biggr) +2&=\biggl(\prod_{k=0}^{n-2} F_k \biggr) \times F_{n-1} +2 \\&=\biggl(F_{n-1}-2 \biggr) \times F_{n-1} +2 \\&=\biggl(2^{2^{n-1}}+1-2 \biggr) \times \biggl(2^{2^{n-1}}+1 \biggr) +2 \\&=\biggl(2^{2^{n-1}}-1 \biggr) \times \biggl(2^{2^{n-1}}+1 \biggr) +2 \\&=2^{2^n}-1+2 \\&=2^{2^n}+1=F_n \end{aligned}

We now show that any pair of Fermat numbers are relatively prime. Suppose that m is a common divisor for F_j and F_n where j<n. Then m divides both \displaystyle \prod_{k=0}^{n-1} F_k and F_n. Because of the recursive relation (1), m divides 2. Since the Fermat number F_n is an odd integer, m cannot be 2. Thus m=1.

Thus the Fermat numbers satisfy Theorem 1.

See here for a generalization of the proof in this post, without the Fermat number point of view.

___________________________________________________________________________________________________________________

Reference

  1. Aigner, M., Gunter, M.Z. Proofs from THE BOOK, third edition, Springer-Verlag, Berlin, 2004.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Euclid’s Proof of the Infinitude of Primes

The oldest known proof that there are infinite number of primes is the one that is due to Euclid (around 300 BC). It is probably the most accessible. So I start the blog by stating this proof.

________________________________________________________

Theorem. There are infinitely many prime numbers.

The strategy is to show that given a finite list of prime numbers \left\{p_1, p_2, \cdots, p_n \right\}, we can always find another prime number not on the list.

Let n=p_1 \times p_2 \times \cdots \times p_n. Let p be a prime divisor of n+1. If p is on the list \left\{p_1, p_2, \cdots, p_n \right\}, then p would divide both n+1 and n. This means that p would divide 1 (the difference of n and n+1). This is impossible. So p must a prime number not on the original list. Hence there must be infinitely many prime numbers.

________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

\text{ }