Infinitude of Primes

$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: there are infinitely many primes.

Proof

Assume to the contrary that the number of primes is finite. Let these be $p_{1}, p_{2}, \ldots , p_{n}$. We are then able to form a number $M = p_{1}p_{2}\cdot \ldots \cdot 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_{1}, p_{2}, \ldots , 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, \ldots , n\}.$ And let $I^{c} = \{0, 1, 2, \ldots , n\} \setminus I$, the complement of $I$ in the segment. Denote $p_{0} = 1$. Define

$\displaystyle K = \prod_{i\in I} p_{i} + \prod_{i\in I^{c}} p_{i}. $

Then $K$ is divisible by or is equal to a prime distinct from $p_{1}, \ldots , 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 $\mbox{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, \ldots$, 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_{1}, p_{2},\ldots , p_{n}$ of primes in the form $4m - 1$. Form a number $N = 4p_{1}p_{2}\cdot\ldots\cdot 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_{1}, p_{2}, \ldots , 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.
V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012
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

71536781