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

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71471616