# 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

70387165