Infinitude of Primes

The distributive law

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

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.

Proof

Let there be only a finite number of primes: 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 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

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 2

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.

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

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

Reference

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

• Infinitude of Primes
  1. Infinitude of Primes - A Topological Proof
  2. Infinitude of Primes - A Topological Proof without Topology
  3. Infinitude of Primes Via *-Sets
  4. Infinitude of Primes Via Coprime Pairs
  5. Infinitude of Primes Via Fermat Numbers
  6. Infinitude of Primes Via Harmonic Series

Copyright © 1996-2009 Alexander Bogomolny