Euclid's Theorem on the Infinitude of Prime Numbers

Prime numbers are infinite because for any given prime number P, there always exists a larger prime.

To prove that there are infinitely many prime numbers, Euclid constructs a new number that cannot be divisible by any existing prime numbers, leading to the conclusion that new prime numbers must exist.

The Proof
A Practical Example
An Alternative Proof

The Proof

Euclid's key idea is to assume that a prime number $ P $ is the largest of all.

He calculates the product of all prime numbers up to $ P $ and adds 1:

$$ n = (2 \times 3 \times 5 \times... \times P)+1 $$

This new number $ n $ is not divisible by any of the primes up to $ P $ because it always leaves a remainder of 1.

Moreover, since we added 1, we know that $ n $ is greater than $ P $:

$$ n > P $$

At this point, there are two possibilities:

If $ n $ is a prime number, then $ P $ is not the largest prime.
If $ n $ is composite, it must have at least one prime factor. Since we already established that $ n $ is not divisible by any of the primes up to $ P $, there must be another prime $ P' $ greater than $ P $. This contradicts our assumption that $ P $ was the largest prime.

In both cases, our initial assumption is proven false: $ P $ is not the largest prime.

Therefore, the opposite must be true: for any given prime $ P $, there always exists a larger prime.

From this, we conclude that prime numbers are infinite.

Note: In some versions of Euclid's proof, 1 is added, while in others, 1 is subtracted. The result remains the same. In both cases, divisibility by all primes up to $ P $ is broken, ensuring that the resulting number $ n $ is not divisible by any of them.

A Practical Example

Let's assume, for the sake of argument, that 5 is the largest prime number.

The prime numbers up to 5 are: $ 2, 3, 5 $. We compute their product and add 1:

$$ n = (2 \times 3 \times 5) + 1 = 30 + 1 = 31 $$

The number $ n = 31 $ is not divisible by any of the primes up to 5, as division always leaves a remainder of 1.

31 is not divisible by 2, since $ 31 \div 2 = 15 $ with a remainder of 1.
31 is not divisible by 3, since $ 31 \div 3 = 10 $ with a remainder of 1.
31 is not divisible by 5, since $ 31 \div 5 = 6 $ with a remainder of 1.

Since 31 is not divisible by any of the primes up to 5, there are two possible conclusions:

If $ n = 31 $ is prime, then $ P = 5 $ is not the largest prime.
If $ n = 31 $ is not a prime, then it must be divisible by some other prime. Since $ n $ is not divisible by any of the primes up to $ P $, there must exist another prime $ P' > P $.

In both cases, we have shown that $ P = 5 $ is not the largest prime.

Note: In this case, $ n $ is itself a prime number. However, even if it were not, the proof would still demonstrate the existence of a prime greater than $ P $. For example, with $ P = 13 $, we get:

$$ n = (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031 $$

The number $ n = 30031 $ is not prime, but it is divisible by $ P' = 59 $, which is greater than $ P = 13 $. So even in this case, there exists a prime larger than $ P $.

An Alternative Proof

Let's assume we have three prime numbers $ a, b, c $ and aim to prove the existence of a fourth prime.

$$ a, b, c \in P $$

We construct a new number $ d $:

$$ d = abc + 1 $$

If $ d $ is a prime number, then we have proven the theorem:

$$ d \in P $$

If $ d $ is not a prime, then there must exist some prime $ d' $ that divides $ abc $:

$$ d \notin P \rightarrow d' | abc $$

In this case:

If $ d' $ is different from $ a, b, c $, then we have found a new prime, proving the theorem.
$$ d' \ne (a \land b \land c ) $$
If $ d' $ is equal to one of the primes $ a, b, c $, then it should also divide the difference between $ abc $ and $ abc+1 $, which is 1. However, this is impossible.
$$ d' = ( a \lor b \lor c ) \rightarrow \:\: contradiction $$

Therefore, if $ d' $ is a prime, it must be different from $ a, b, c $, proving the existence of another prime.

Note: This confirms that the sequence of prime numbers is infinite. The same theorem can be generalized by considering $ n $ prime numbers where

$$ d = p_1 + ... + p_n + 1 $$

and proving the existence of an additional prime $ p_{n+1} $.