Infinitude of Primes

The distributive law

a(b + c) = ab + ac

tells us that if two numbers N (= ab) and M (= ac) are divisible by a number a, so will be their sum. For M negative (= -ac), we may replace the law with

a(b - c) = ab - ac

which makes the same assertion but now for the difference. From here, no two consecutive integers have a common factor: if N - M = 1, N and M are mutually prime. This fact has been used by Euclid in his Elements to prove infinitude of primes (Elements, Proposition IX.20):

Proposition

Prime numbers are more than any assigned multitude of prime numbers.

In other words, the number of primes is infinite.

Proof

Assume to the contrary that the number of primes is finite. Let these be p₁, p₂, ...,p_n. We are then able to form a number M = p₁p₂· ... ·p_n equal to the product of all existent prime numbers. M is clearly divisible by any of the existent primes p_i.

Let N = M + 1. Whatever divisors N may have none of them may be among the divisors of M. Consider N's prime factors. From the previous discussion none of them may coincide with any of p₁, p₂, ..., p_n. This contradicts the assumption that the number of primes is finite.

Remark 1

The argument can be cast a little differently. By definition, M is divisible by any prime number in existence. N, being larger than any existent prime is divisible by some of them. Let p_k be a divisor of N. Then p_k divides N - M = 1, a contradiction.

Remark 2

More than 2000 years later, Andrew Cusumano, Underwood Dudley, and Clayton Dodge found a generalization of Euclid's argument (Am Math Monthly, v 115 (2008), n 7, p.663). Let I be any subset of the segment of integers {0, 1, 2, ..., n}. And let I^c = {0, 1, 2, ..., n} \ I, the compelement of I in the segment. Denote p₀ = 1. Define

K = Π_i∈I p_i + Π_i∈I^c p_i.

Then K is divisible by or is equal to a prime distinct from p₁, ..., p_n. Euclid's proof is obtained with I = {0}.

Remark 3

Harry Fürstenberg of the Hebrew University of Jerusalem, Israel gave a startling proof of the infinitude of primes that, of all things, employs basic notions of topology.

We already used the distributive law argument to prove a complementary fact that, in the sequence of all integers, there exist arbitrary long runs with no prime numbers. So it appears that, among all integers, the primes are distributed in a highly irregular manner. Legendre (1752-1833) suggested that the the number of primes below a given number K is roughly ln(K), the natural logarithm of K. Legendre's hypothesis has been proven in 1896 independently by the French J. Hadamard (1865-1963) and Belgian C.J. de la Vallée-Poussin.

Lejeune Dirichlet (1805-1859) has generalized Euclid's result by proving that any arithmetic sequence a, a + d, a + 2d, ... with a and d mutually prime contains an infinite number of primes. Some special cases of the Dirichlet's theorem are easy to prove. For example, let a = 3 and d = 4.

Divided by 4, integers may have only four remainders: 0, 1, 2, 3. Accordingly, they may be written as 4m, 4m + 1, 4m + 2, 4m + 3. Numbers 4d and 4d + 2 are divisible by 4 and 2, respectively, and thus can't be prime (except for 2).

Now, numbers 4d + 1 have the property that the product of any two of them is again a number in the same form: (4k + 1)(4m + 1) = 4(k + m + 4km) + 1. Also note that numbers in the form 4m + 3 may also be written as 4m + 3 = 4(m + 1)-1 = 4k - 1. Now, as before, assume there is only a finite number p₁, p₂,... , p_n of primes in the form 4m - 1. Form a number N = 4p₁p₂·...·p_n - 1. Since N itself is in the form 4m - 1, all of its prime factors can't be in the form 4m+1. Therefore, there must be at least one in the form 4m - 1. Whatever it is, it must be different from any of p₁, p₂, ..., p_n. Contradiction.

Remark 4

Similar proofs work for numbers 3d + 2 and 6d + 5.

Reference

J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
R.Courant and H.Robbins, What is Mathematics?, Oxford University Press, 1966.
H.Davenport, The Higher Arithmetic, Harper&Brothers, NY
U. Dudley, Elementary Number Theory, Dover, 2008
W.Dunham, Journey through Genius, Penguin Books, 1991
W.Dunham, The Mathematical Universe, John Wiley & Sons, NY, 1994.
H.Eves, Great Moments in Mathematics Before 1650, MAA, 1983
M.Kac and S.M.Ulam, Mathematics and Logic, Dover Publications, NY, 1968.
Oystein Ore, Number Theory and Its History, Dover Publications, 1976
J.A.Paulos, Beyond Numeracy, Vintage Books, 1992
H.Rademacher and O.Toeplitz, The Enjoyment of Mathematics, Dover Publications, 1990.

Infinitude of Primes

40614748