Number Theory: A Very Short Introduction

form . It follows in either case that there’s a prime of the form other than p₁, p₂, …, and p_n, and this contradiction shows that there must be infinitely many prime numbers of this form.

We can imitate this proof to show that there are infinitely many prime numbers of the form . We assume that there are only finitely many primes, p₁, p₂, …, p_n, of this form, but this time we consider the number

noting that multiplying any numbers of the form always gives another one. We deduce that there are infinitely many primes of the form .

We can also adapt Euclid’s proof to deduce that there are infinitely many primes of certain other forms. But we cannot use this approach to prove that there are infinitely many primes of the form , because such numbers can also be obtained by multiplying only numbers of the form : for example, . We’re likewise unable to adapt this approach to prove that there are infinitely many primes of the form , because such numbers can be obtained by multiplying only numbers of the form : for example, .

But there are indeed infinitely many prime numbers of the form , and we can prove this by recalling from Chapter 4 that if −1 is a square (mod p), then p must be a prime of the form . To get a contradiction we’ll assume that there are finitely many primes, p₁, p₂, …, p_n, of the form , and this time we’ll consider the number

which certainly has the form . As before, none of our primes p₁, p₂, …, p_n can divide N, so N is either a new prime or is a product of new primes. In either case there’s a new prime, which we’ll call p, that divides N. It follows that

−1 is a square (mod p) and we deduce that p has the form so . This contradiction proves there must be infinitely many primes of the form . A similar proof shows that that there are infinitely many primes of the form .

Having shown that there are infinitely many primes of these forms, we may now ask whether there are infinitely many prime numbers of the form , for any given numbers a and b. In its most general form, the answer to this question is ‘no’, for if a and b have a common factor d that’s greater than 1, then d must also divide all numbers of the form . For example, there are no primes of the form (because all such numbers have 2 as a factor) or of the form (because all such numbers have 3 as a factor).

But if a and b are coprime, then we have the following result, conjectured in 1785 by Legendre and proved in 1837 by Lejeune Dirichlet.

Dirichlet’s theorem: If a and b are given numbers with , then there are infinitely many prime numbers of the form , where q is an integer.

For example, there are infinitely many prime numbers of the form , because , and there are infinitely many prime numbers of the form , because . Also, because , there are infinitely many prime numbers of the form —that is, there are infinitely many primes with final digit 9—and likewise there are infinitely many primes with final digit 1, 3, or 7.

An arithmetic progression with first term b and common difference k is a finite or infinite sequence of equally spaced numbers of the form

For example, the sequence of numbers

is a finite arithmetic progression with first term and common difference , and the sequence

of numbers of the form is an infinite arithmetic progression with first term and common difference . More generally, the sequence of numbers of the form is an infinite arithmetic progression with first term b and common difference a, and if , then such a sequence must include infinitely many primes, by Dirichlet’s theorem.

Let’s now turn the above question around. The sequence

is an arithmetic progression of five primes with first term 5 and common difference 6, but it cannot be extended to an arithmetic progression of six primes because the next term is the composite number . An example of an arithmetic progression of six primes is

More generally, we can ask:

Does the list of primes contain arithmetic progressions of any chosen length n?

As we’ve just seen, the answer to this is ‘yes’ when and 6. For , the following arithmetic progression with first term 199 and common difference 210 consists entirely of primes:

Likewise, for , the arithmetic progression with first term 56,211,383,760,397 and common difference 44,546,738,095,860 consists entirely of primes. At the time of writing, the longest known arithmetic progressions of primes contain 26 primes.

The general question was answered in the affirmative by Ben Green and Terry Tao in 2004:

The Green–Tao theorem: Given any number n, the list of prime numbers contains an arithmetic progression of n primes.

Unique factorization

In Chapter 3 we saw that the factorization of positive integers into primes is unique, apart from the order of the factors—it’s a basic property of our number system. But it doesn’t hold for certain other systems of numbers. Here are two examples:

Example 1. Consider just the positive even numbers (which we’ll call e-numbers),

and consider the factorization of e-numbers into smaller e-numbers. We’ll call an e-number e-composite if it can be