Euclid’s Proof: Why There Are Infinitely Many Prime Numbers in Simple Terms

Prime numbers are like the building blocks of all whole numbers – integers greater than 1 that have no divisors other than 1 and themselves. Examples include 2, 3, 5, and 7 (note that 2 is the only even prime number).

But how do we know there are infinitely many primes? Euclid, the great Greek mathematician, provided a beautiful argument to prove that they are endless.

The core of Euclid's proof is a "proof by contradiction," where you:

1. Assume the opposite of what you want to prove.
2. Show that this assumption leads to an impossible situation.
3. Conclude that the assumption must be false, proving the original claim.

In this case, we want to prove there are infinitely many primes. So, let’s assume the opposite: that there are only a finite number of primes.

Step 1: Assume a Finite List of Primes
Let’s suppose we have a complete, finite list of all prime numbers: p1, p2, ..., pk. For example, this list could be 2, 3, 5, ... up to some last prime pk.

If our assumption is correct, no more primes exist beyond this list.

Step 2: Construct a New Number
Now comes the clever part. We will construct a new number, N, using all the primes in our list. Multiply them together and add 1:

N = p1 × p2 × p3 × ... × pk + 1.

For example, if our primes were 2, 3, and 5, then N would be:

N = 2 × 3 × 5 + 1 = 30 + 1 = 31.

Step 3: What Makes N Special?
This number N has two key properties:

• N is greater than any prime in our list.
  
• Most importantly, N is not divisible by any of the primes in our list.

Why Isn’t N Divisible by Any Primes?
If you divide N by any prime pi from the list, you get a remainder of 1. This is because:

N = (p1 × p2 × ... × pk) + 1.

The product part (p1 × p2 × ... × pk) is exactly divisible by pi, but adding 1 leaves a remainder of 1.

For example, let’s say our list of primes is 2, 3, and 5. Then:

• P = 2 × 3 × 5 = 30.
  
• N = P + 1 = 30 + 1 = 31.

When you divide 31 by any of the primes in the list:

• 31 ÷ 2 = 15 remainder 1.
  
• 31 ÷ 3 = 10 remainder 1.
  
• 31 ÷ 5 = 6 remainder 1.

In each case, the remainder is 1, so N is not divisible by 2, 3, or 5. Therefore, N must either be a new prime or have a prime factor not in the original list.

Step 4: The Contradiction

This leads to a contradiction. If our list was supposed to contain all primes, then we shouldn’t be able to find a number like  that either is a new prime or has a new prime factor. But we did, so our original assumption must be false.

Therefore, the prime numbers cannot be finite. There must be infinitely many prime numbers.
hashtaghashtag