Proofs of the infinitude of primes

Tomohiro Yamada

Abstract

In this document, I would like to give several proofs that there exist infinitely many primes.

0 Introduction

It is well known that the number of primes is infinite.

In this document, I would like to give several proofs of this theorem. Many of these proofs give poor estimates for the number of primes below a given number. Let π(x) denote the number of primes below a given number x. Then many proofs give estimates such that π(x) > c log x for some constant c > 0.

Literatures can be found by the search result of MathSciNet by “infinitude of prime∗”.

Of course, there are more proofs of the infinitude of primes. I would like to add such proofs later.

1 Euclid’s proof

Suppose that 2 = p_{1} < p_{2} < ⋯ < p_{r} are all of the primes. Let P = p_{1}p_{2} ⋯ p_{r} + 1 and p be a prime dividing P. Since none of p_{1}, p_{2}, …, p_{r} divides P = p_{1}p_{2} ⋯ p_{r}+1, p must be another prime. Therefore p_{1}, p_{2}, …, p_{r} cannot be all of the primes.

Euclid’s proof will be the most popular proof of the infinitude of primes.

It is very simple. Moreover, Euclid’s proof can be modified so that it gives an information on the distribution of primes; there exists a prime p with R < p ≤ R^{R} + 1 for any R ≥ 2.

Suppose that 2 = p_{1} < p_{2} < ⋯ < p_{r} are all of the primes below R. Let P = p_{1}p_{2} ⋯ p_{r} + 1 and p be a prime dividing P. Since none of p_{1}, p_{2}, …, p_{r} divides P = p_{1}p_{2} ⋯ p_{r} + 1, p must be another prime. We clearly have p ≤ R^{r} + 1 ≤ R^{R} + 1. Since p_{1}, p_{2}, …, p_{r} are all of the primes below R, we see that p > R.

We can see that R^{R} + 1 can be replaced by R^{R/2+1} + 1, finding that the number of primes below R cannot exceed R/2 + 1 since 1 and all even integers other than 2 cannot be prime.

Of course, it is very poor result.

We note that a number of the form p_{1}p_{2} ⋯ p_{r} +1 is not necessarily itself prime. Indeed, we see that 2 × 3 × 11 × 13 + 1 = 59 × 509. It is unsolved whether there exists infinitely many primes of the form p_{1}p_{2} ⋯ p_{r} + 1. It is also unknown whether there exists infinitely many composites of the form p_{1}p_{2} ⋯ p_{r} + 1.

Euclid’s proof has many variants.

References:

P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, New York, 1996, p.p. 3–4.

L. E. Dickson, History of the Theory of Numbers, Vol. I: Divisibility and Primality, Carnegie Institution of Washington, 1919 (reprint: Dover Publication, New York, 2005), p. 413.

2 Kummer’s proof

Suppose that 2 = p_{1} < p_{2} < ⋯ < p_{r} are all of the primes. Let N = p_{1}p_{2} ⋯ p_{r} > 2. The integer N−1 > p_{r}, being a product of primes, must have a prime divisor p_{i}. So p_{i} divides N − (N − 1) = 1, which is impossible.

Kummer’s proof is essentially the same as Euclid’s one. Kummer’s uses p_{1}p_{2} ⋯ p_{r} − 1 while Euclid’s uses p_{1}p_{2} ⋯ p_{r} + 1. Similar to Euclid’s proof, Kummer’s proof can be modified to show that there exists a prime p with R < p ≤ R^{R/2+1} − 1 for any R ≥ 2.

Ref.: P. Ribenboim, op. cit., p. 4 and L. E. Dickson, op. cit., p. 413.

3 Stieltjes’ proof

Assume that p_{1}, p_{2}, …, p_{r} are the only primes. Let N = p_{1}p_{2} ⋯ p_{r} and let N = mn be any factorization of N with m, n ≥ 1. Since each prime p_{i} divides exactly one of m and n, none of p_{i}’s divides m + n. This means m + n is divisible by none of the existing primes, which is impossible since m + n > 1.

Ref.: P. Ribenboim, op. cit., p. 4 and L. E. Dickson, op. cit., p. 414.

4 Goldbach’s proof

We begin by showing that the Fermat numbers F_{n} = 2^{2^{n}} + 1(n ≥ 0) are pairwise coprime. Indeed, we see that F_{m}−2 = 2^{2^{n}} −1 = (2^{2^{n}−1}+1)(2^{2^{n}−1}− 1) = F_{0}F_{1} ⋯ F_{m−1}. Therefore any prime dividing both F_{m} and F_{n}(m > n) must divide 2 = F_{m} − (F_{m} − 2). However, there can be no such prime since F_{n} is odd for any n.

So, if q_{1} is a prime dividing F_{1}, q_{2} is a prime dividing F_{2}, …, then q_{1}, q_{2}, … is an infinite sequence of primes.

Part 8, Problem 94 of the book of Pólya and Szegö indicates this proof. However, they are not the first to have this idea. It is written in p. 4 of Ribenboim’s book:

Nobody seems to be the first to have a good idea – especially if it is simple. I thought it was due to Pólya and Szegö (see their book, 1924). E. Specker called my attentino to the fact that Pólya used an exercise by Hurwitz (1891). But, W. Narkiewirz just told me that in a letter to Euler (July 20/31, 1730), Goldbach wrote the proof given below using Fermat numbers – this may well be the only written proof of Goldbach.

Explicitly, the first Fermat numbers are F_{0} = 3, F_{1} = 5, F_{2} = 17, F_{3} = 257, F_{4} = 65537, each of which is itself prime. However, F_{5} = 4294967297 = 641 is composite. So are many other Fermat numbers while no Fermat primes other than the above five primes is known.

Ref.: P. Ribenboim, op. cit., p.p. 4–5 and L. E. Dickson, op. cit., p. 413.

5 Schorn’s proof

Assume that there exist only m primes and let n = m + 1. We note the n integers (n!)i + 1(i = 1, 2, …, n) are pairwise coprime. Indeed, if 1 ≤ i < j ≤ n and j = i + d, then ((n!)i + 1, (n!)j + 1) = ((n!)i + 1, (n!)d) = 1. Let p_{i} be a prime dividing (n!)i + 1 for each i = 1, 2, …, n. Then p_{1}, p_{2}, …, p_{n} must be distinct primes. Therefore there exist at least n prime numbers, which is absurd.

Schorn’s proof shows that there exist at least n primes below (n!)n + 1 for any integer n.

Ref.: P. Ribenboim, op. cit., p. 5.

6 Euler’s proof

Euler’s proof uses a rather analytic idea while many proofs of the infinitude of primes are elementary. However, Euler’s method leads to important developments on the distribution of primes.

Suppost that p_{1}, p_{2}, …, p_{n} are all of the primes. Since each p_{i} > 1, the sum of the geometric series ∑_{k=0}^{∞} 1/p_{i}^{k} is 1/(1 − 1/p_{i}).

Hence ∏_{i=1}^{n} 1/(1 − 1/p_{i}) = ∏_{i=1}^{n} ∑_{k=0}^{∞} 1/p_{i}^{k}. The right-hand side is the sum of all positive integers, each counted at least once, since p_{1}, p_{2}, …, p_{n} are all of the primes. Therefore ∑_{n=1}^{∞} 1/n ≤ ∏_{i=1}^{n} 1/(1 − 1/p_{i}) must be finite. However, it is well known that ∑_{n=1}^{∞} 1/n is divergent (we can see this by ∑_{n=1}^{∞} 1/n ≥ 1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + ⋯) This is a contradiction.

Indeed, Euler obtains the well-known formula that ∑_{n=1}^{∞} 1/n^{s} = ∏_{i=1}^{n} 1/(1− 1/p_{i}^{s}) using the fundamental theorem of arithmetic.

An interesting point of Euler’s method lies on indicating the link between the zeta function ζ(s) = ∑_{n=1}^{∞} 1/n^{s} and the prime numbers. This is one of the most important basis of analytic number theory.

Euler further shows that the reciprocals of the prime is divergent.

We see that ∑_{n=1}^{N} 1/n ≤ ∏_{p≤N} 1/(1 − 1/p) for any integer N since any integer ≤ N must have a prime divisor ≤ N. Now log ∏_{p≤N} 1/(1 − 1/p) = − ∑_{p≤N} log(1 − 1/p), and for each prime p we have log(1 − 1/p) = ∑_{m=1}^{∞} 1/(mp^{m}) ≤ ∑_{m=1}^{∞} 1/(p^{m}) = 1/p + 1/p(p − 1) < 1/p + 1/(p − 1)^{2}. Hence, log ∑_{n=1}^{N} 1/n ≤ ∑_{p≤N} 1/p + 1/(p − 1)^{2} ≤ ∑_{p≤N} 1/p + ∑_{n} 1/n^{2}.

This shows that ∑_{p≤N} 1/p ≥ log ∑_{n=1}^{N} 1/n − c ≥ log log N − C for some constants c and C.

Ref.: P. Ribenboim, op. cit., p.p. 6–7 and L. E. Dickson, op. cit., p. 413.

7 Erdős’ proof

Erdős gave an elementary proof of divergence of the sum of reciprocals of primes.

Let p_{1} = 2, p_{2} = 3, …, p_{j} be all primes below x. Let n = n_{1}^{2}m with m squarefree. Then m = 2^{b_{1}}3^{b_{2}} ⋯ p_{j}^{b_{j}} with every b_{i} either 0 or 1. There exists at most 2^{j} such integers. For each fixed m, the number of possibility of n_{1} is at most x^{1/2} since n_{1}^{2} ≤ n ≤ x. Thus we have x ≤ 2^{j}x^{1/2}, or, equivalently, j ≤ (log x)/(2 log 2). So that there exist at least (log x)/(2 log 2) prime numbers below x.

Using Erdős’ argument, we can also prove that the reciprocals of the prime is divergent.

Assume that there exists a number M such that ∑_{p>M} 1/p < 1/2. Then we have ∑_{p>M} N/p < N/2 for any integer N.

Now divide the positive integers below N into two sets. Let N_{1} be the number of positive integer below N which can be divisible by some prime > M and N_{2} be the number of remaining integers below N.

Then we have N_{1} ≤ ∑_{p>M} N/p < N/2. Moreover, we have N_{2} < 2^{M}N^{1/2} by repeating the argument given above. So that N = N_{1} + N_{2} < N/2 + 2^{M}N^{1/2} < N if we take N sufficiently large. This is absurd.

Indeed, we can take N = 2^{2M+2} for an arbitrary integer M > 0. Then N_{1} ≤ ∑_{M<p≤N} N/p and N_{1} = N − N_{2} ≥ N − 2^{M}N^{1/2} = 2^{2M+1} = N/2, so that ∑_{M<p≤2^{2M+2}} 1/p > 1/2.

Ref.: G. H. Hardy and E. M. Wright, D. R. Heath-Brown, J. Silverman, A. Wiles, An Introduction to the Theory of Numbers, the 6th edition, Oxford University Press, 2008, Section 2.6.

8 Chebysheff’s proof

Chebysheff used the arithmetic property of the factorials to prove his celebrated theorem that there always exists a prime p with x < p < 2x for x > 1. Erdős gave a simple proof.

Chebysheff’s argument can be used to give a simple proof of the infinitude of primes.

Let a(p, N) be the exponent of prime p dividing the factorial N!.

Then we have a(p, N) = ⌊N/p⌋+⌊N/p^{2}⌋+⋯ < N/(p−1) for any prime p and a(p, N) = 0 for p > N.

So that ∑_{p≤N}(log p)/(p − 1) > ∑_{p} a(p, N)(log p)/N = (1/N) log(N!) > (log N)−1. Therefore the sum ∑_{p≤N}(log p)/(p−1) tends to infinity together with N. This clearly implies the infinitude of primes.

Ref.: G. H. Hardy and E. M. Wright, D. R. Heath-Brown, J. Silverman, A. Wiles, An Introduction to the Theory of Numbers, the 6th edition, Oxford University Press, 2008, Section 22.7.

9 Srinivasan’s proof

As mentioned above, any infinite sequence of pairwise coprime integers shows the infinite of primes.

If the sequence x_{i} satisfies x_{i} | x_{i+1} and gcd(x_{i}, x_{i+1}/x_{i}) = 1, then we immediately see that the sequence x_{i+1}/x_{i} contains no two integers which has a nontrivial common divisor.

Let f(x) = x^{2} +x+1. Then f(n^{2}) = f(n)f(−n) and gcd(n^{2} +n+1, n^{2} − n+1) = 1. Indeed, n^{2} +n+1 must be odd and d | gcd(n^{2} +n+1, n^{2} −n+1) implies d | 2n, d | n, thus d = 1. So that the sequence f(2^{2^{m}}) works.

The sequence x_{m} = 2^{p^{m}} − 1 also works. We see that q | x_{m} implies x_{m+1}/x_{m} = ((x_{m}+1)^{p}−1)/((x_{m}+1)−1) = 1+(x_{m}+1)+⋯+(x_{m}+1)^{p−1} ≡ p (mod q). So that if a prime q divides x_{m} and x_{m+1}/x_{m}, then q = p, which is impossible since x_{m} = (2^{m})^{p} − 1 ≡ 1 (mod p) by Fermat’s theorem.

We note that the prime factor 2^{p^{m}}−1 must be ≡ 1 (mod p^{m}). Therefore, this shows that there are infinitely many primes ≡ 1 (mod p^{m}).

Srinivasan also shows that there are infinitely many primes ≡ 1 (mod k) for every integer k ≥ 1 using the same method. Actually, this is essentially a variant of Lucas’ argument showing that there are infinitely many primes ≡ 1 (mod k) for every integer k ≥ 1.

Ref.: S. Srinivasan, On infinitude of primes, Hardy Ramanujan J. 7 (1984), 21–26.

10 Thue’s proof

Let n, k ≥ 1 be integers satisfying (1 + n)^{k} < 2^{n} and p_{1} = 2, p_{2} = 3, …, p_{r} be all primes ≤ 2^{n}. Every integer m, 1 ≤ m ≤ 2^{n} can be written in the form m = 2^{e_{1}}3^{e_{2}} ⋯ p_{r}^{e_{r}}. It is clear that every e_{i} ≤ n since m ≤ 2^{n}. Since the number of such choices of e_{1}, e_{2}, …, e_{r} is at most (n + 1)^{r}, we have (1 + n)^{k} < 2^{n} ≤ (1 + n)^{r}. So that r > k. For every integer k ≥ 1, we have (1 + 2k^{2})^{k} < 2^{2k^{2}} since 1 + 2k^{2} < 2^{2k}. Thus we can choose n = 2k^{2} for every integer k ≥ 1. It follows that there exist at least k + 1 primes p < 2^{n} = 4^{k^{2}}.

Ref.: P. Ribenboim, op. cit., p. 7 and L. E. Dickson, op. cit., p. 414.

11 Perott’s proof

First we note that ∑_{n=1}^{∞}(1/n^{2}) is convergent with sum smaller than 2. Indeed, it is a well-known result of Euler that the sum is exactly π^{2}/6. A simple and elementary argument gives that ∑_{n=1}^{∞}(1/n^{2}) < 7/4 since

∑_{n=1}^{∞}(1/n^{2}) = 1+1/4+∑_{n=3}^{∞}(1/n^{2}) < 5/4+∑_{n=3}^{∞}(1/n(n−1)) = 5/4+∑_{n=3}^{∞}(\frac{1}{n − 1}−\frac{1}{n}) = 5/4+1/2 = 7/4.

Let X > 0 be an arbitrary real number and let δ = 2 − ∑_{n=1}^{∞}(1/n^{2}).

The above estimate gives δ > 1/4. Let p_{1}, p_{2}, …, p_{r} be all primes ≤ X. The number of integers m ≤ X not divisible by a square is therefore at most 2^{r}. The number of integers m ≤ X divisible by d^{2} is at most X/d^{2}, so that the number of integers m ≤ X divisible by some square is at most ∑_{d=2}^{∞}(X/d^{2}) = X(∑_{d=1}^{∞}(X/d^{2}) − 1) = X(1 − δ). Therefore X ≤ 2^{r} + X(1 − δ). Thus 2^{r} ≥ δX ≥ X/4. This gives r > (log X/ log 2) − 2.

Perott’s proof counts that the number of integers m ≤ X not divisible by a square by excluding the set of integers m ≤ X divisible by each square d^{2}. This argument is essentially the basis of sieve theory developed to provide estimates for the number of integers satisfying given conditions.

Ref.: P. Ribenboim, op. cit., p. 8 and L. E. Dickson, op. cit., p. 413.

12 Auric’s proof

Suppose that p_{1} < p_{2} < ⋯ < p_{r} are all of the primes. Let t ≥ 1 be any integer and N = p_{r}^{t}.

Each positive integer m ≤ N is written as m = p_{1}^{f_{1}}p_{2}^{f_{2}} ⋯ p_{r}^{f_{r}} with the r-tuple (f_{1}, f_{2}, …, f_{r}) uniquely defined. Letting E = (log p_{r})/(log p_{1}), we have f_{i} ≤ tE since p_{1}^{f_{i}} ≤ p_{i}^{f_{i}} ≤ N = p_{r}^{t} for every i. Thus N is at most the number of r-tuples (f_{1}, f_{2}, …, f_{r}) and therefore p_{r}^{t} = N ≤ (tE + 1)^{r} ≤ t^{r}(E + 1)^{r}, which is clearly impossible for sufficiently large t.

Ref.: P. Ribenboim, op. cit., p. 9 and L. E. Dickson, op. cit., p. 414.

13 Boije af Gennäs’ proof

Let X > 0 be an arbitrary real number and 2, 3, …, p_{n} be all primes ≤ X. Take P = 2^{e_{1}}3^{e_{2}} ⋯ p_{n}^{e_{n}} with each e_{i} ≥ 1. Write P as a product of relatively prime factors δ, P/δ, where Q = P/δ − δ > 1. Since Q is divisible by no prime ≤ X, it must be a product of primes > X. In particular, there exists a prime > X.

Ref.: L. E. Dickson, op. cit., p. 414.

14 Barnes’ proof

In 1976, Barnes published a new proof of the infinitude of primes using the theory of periodic continued fractions and the theory of Pellian equations.

Let p_{1} = 2, p_{2} = 3, …, p_{t} be all of the primes and P = ∏_{i=1}^{t} p_{i}, Q = ∏_{i=2}^{t} p_{i}. Consider the continued fraction x = [p, p, …]. Then we have x = (P + \sqrt{P^{2} + 4})/2 = Q + \sqrt{Q^{2} + 1}.

Now Q^{2} + 1 must be a power of two and therefore Q^{2} + 1 = 2^{2l+1} or Q^{2} − 2(2^{l})^{2} = −1. This means that Q/2^{l} is an even approximant of [1, 2, 2, …], the continued fraction for \sqrt{2}. Denote the denominator of the approximants by B_{m}. Thus we have B_{0} = 1, B_{1} = 2, B_{m+1} = 2B_{m} + B_{m−1} and B_{m} must be odd for even m. Thus l = 0 and Q = 1. This is a contradiction.

Of course Q^{2} + 1 cannot be a power of two since Q^{2} + 1 > 2 and Q^{2} + 1 cannot be divisible by 4.

Ref.: C. W. Barnes, The infinitude of primes; a proof using continued fractions, L’Enseignement Math. (2) 22 (1976), 313–316.

15 Braun’s proof

Suppose that there exist only t primes p_{1}, p_{2}, …, p_{t} and consider the sum m/n = ∑_{i=1}^{t} 1/p_{i}. Now 1/2 + 1/3 + 1/5 > 1, so that m/n > 1 and therefore m > n ≥ 1. Thus m must have a prime factor p_{i}. However, no p_{i} can divide m since p_{i} | m implies p_{i} | p_{1}p_{2} ⋯ p_{i−1}p_{i+1} ⋯ p_{t}. This is a contradiction.

Ref.: L. E. Dickson, op. cit., p. 414.

16 Harris’ proof

Let A_{0}, A_{1}, A_{2} be positive and pairwise coprime integers, and for n ≥ 3 set A_{n} = A_{0}A_{1} ⋯ A_{n−3}A_{n−1} + A_{n−2}. Now we can show that A_{0}, A_{1}, …, A_{n} are pairwise coprime by induction; p | gcd(A_{n}, A_{n−2}) implies p | gcd(A_{n−i}, A_{n−2}) for some i ≥ 1, i ≠ 2 (as p | A_{n} − A_{2} = A_{0}A_{1} ⋯ A_{n−3}A_{n−1}) and p | gcd(A_{n}, A_{n−j}) for some j ≥ 1, j ≠ 2 implies p | gcd(A_{n−j}, A_{n−2}) (as p | A_{n} − A_{0}A_{1} ⋯ A_{n−3}A_{n−1} = A_{n−2}). Since A_{n} > 1 at least for n ≥ 3, we see that A_{0}, A_{1}, … contains an infinite set of integers > 1 no two of which has a common prime factor. Therefore the number of primes is infinite.

We note that taking the sequence b_{i}(i ≥ 0) such that A_{0} = b_{0}, A_{1} = b_{0}b_{1} + 1, A_{2} = b_{0}b_{1}b_{2} + b_{0} + b_{2} and b_{n} = A_{0}A_{1} ⋯ A_{n−3}, A_{n} is the numerator of approximants of the regular infinite continued fraction [b_{0}, b_{1}, b_{2}, …].

Ref.: V. C. Harris, Another proof of the infinitude of primes, Amer. Math. Monthly 63 (1956), 711.

17 Chernoff’s proof

Chernoff’s proof uses only a simple enumerating argument. Suppose that there are only k primes p_{1}, p_{2}, …, p_{k}. If N is any positive integer, there are exactly N k-tuples of nonnegative integers (e_{1}, e_{2}, …, e_{k}) satisfying the inequality p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{k}^{e_{k}} ≤ N, or, equivalently, e_{1} log p_{1} + e_{2} log p_{2} + ⋯ + e_{k} log p_{k} ≤ log N. The number of such k-tuples is (log N)^{k}/(k! log p_{1} log p_{2} ⋯ log p_{k}). Therefore N ≤ c(log N)^{k} for some constant c independent of N, which is clearly false. Thus there are infinitely many primes.

We note that we need not use the uniqueness of prime factorization; the fact suffices that there are at most N k-tuples of nonnegative integers (e_{1}, e_{2}, …, e_{k}) satisfying the above inequality.

Moreover, the argument works even if we suppose that there are only k primes p_{1}, p_{2}, …, p_{k} below N. We can take c = 1/(k! log 2) and therefore N ≤ (log N)^{k}/(k! log 2). This gives k > c′(log N) for some positive constant c′.

Ref.: Paul R. Chernoff, A “Lattice Point” Proof of the Infinitude of Primes. Math. Mag. 38 (1965), 208.