Infinitely many proofs that there are infinitely many primes
In Elements IX.20, Euclid gave a proof - a classic example of simplicity and mathematical elegance - of the infinitude of primes. I'll repeat the proof below, with a reference to an earlier page
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.
Most recently, Des MacHale has considered a modification of Euclid's proof. For example, we may consider excluding $2$ from the product but then adding it to the result:
$3+2,$ $3\cdot 5+2,$ $3\cdot 5\cdot 7+2,$ $3\cdot 5\cdot 7\cdot 11+2,\ldots$
The argument is exactly the same: if $3\cdot5\ldots p+2$ were divisible by 2, then so would $3\cdot5\ldots p$, and if it were divisible by any prime below and including $p,$ so would $2$ - a contradiction. It follows that any factor of $3\cdot5\ldots p+2$ is a "new" prime, unaccounted in the sequence $2,3,\ldots,p.$
Naturally, instead of $2$ we can use any other prime, and this leads to another - though not very essentially different - proof of the infinitude of primes.
In the Euclidean proof, we get the sequence
$2+1=3\space\space(prime)\\ 2\cdot 3+1=7\space\space(prime) \\ 2\cdot 3\cdot 5+1=31\space\space(prime) \\ 2\cdot 3\cdot 5\cdot 7+1=211\space\space(prime) \\ 2\cdot 3\cdot 5\cdot 7\cdot 11+1=2311\space\space(prime) \\ 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031 = 59\cdot 509 $
Thus, in the Euclidean proof, it takes six prime factors to arrive at an unlisted prime. If we add $2$ instead of 1, the sequence becomes
$3+2 = 5\space\space(prime)\\ 3\cdot 5+2 = 17\space\space(prime)\\ 3\cdot 5\cdot 7+2 = 107\space\space(prime)\\ 3\cdot 5\cdot 7\cdot 11 = 1157 = 13\cdot 89 $
and it takes only 4 prime factors to get a composite number. Excluding other primes successively we obtain the sequence of first occurrence of the composite numbers: $6,4,5,7,7,4,1,5,1,6,2,1,1,1,9,1,\ldots$ For small primes, $41$ appears a champion with nine factors to produce a composite:
$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 + 41 = 223092911=29^{2}\cdot 265271.$
May this be related to another property of $41$?
Needless to say that, for any one curious, subtracting a prime from the product leads to an additional infinitude of proofs.
Reference
- Des MacHale, Infinitely many proofs that there are infinitely many primes, The Mathematical Gazette, Vol.97 (Novemember 2013) No. 540, 495-498

- 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
72265148