# 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

1. Des MacHale, Infinitely many proofs that there are infinitely many primes, The Mathematical Gazette, Vol.97 (Novemember 2013) No. 540, 495-498  