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: 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
- Infinitude of Primes - A Topological Proof
- Infinitude of Primes - A Topological Proof without Topology
- Infinitude of Primes Via *-Sets
- Infinitude of Primes Via Coprime Pairs
- Infinitude of Primes Via Fermat Numbers
- Infinitude of Primes Via Harmonic Series
- Infinitude of Primes Via Lower Bounds
- Infinitude of Primes - via Fibonacci Numbers
- New Proof of Euclid's Theorem
- Infinitude Of Primes From Legendre's Formula
- Infinitude of Primes - via Bertrand's Postulate
- Infinitude of Primes - An Impossible Injection
- Infinitude of Primes - from Infinitude of Mutual Primes
- Infinitude of Primes Via Euler's Product Formula
- Infinitude of Primes Via Euler's Product Formula for Pi
- Infinitude of Primes Via Powers of 2
- Infinitude of Primes As a Quickie
- A One-Line Proof of the Infinitude of Primes
- Infinitude of Primes - A. Thue's Proof
- Why The Number of Primes Could Not Be Finite?

|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
72260774