How Do We Know Prime Numbers are Infinite?

Proving Euclid’s Theorem

In the last lesson, we discussed the search for large prime numbers including primes 1 billion digits long! If currently the largest known prime number is 17,425,170 long, how do we know these numbers even exist?

Because we can prove they exist! And it’s not as hard as you would think, just an exercise of logic. I’ll show you.

Euclid’s Theorem

There are infinitely many prime numbers.

Suppose I have a list of all the known prime numbers. Let’s show that this list, no matter how large, is incomplete. We’ll show that there always exists a prime number that is not listed.

proof.

Begin with the list of known prime numbers. To generalize, I’ll write the primes as the unknown variables: prime 1, prime 2, prime 3… up through some prime n.

my list of known prime numbers

Let P be the product of the prime number list.

Define the number q as one greater than P.

We can draw two possible conclusions about q:

1. If q is a prime number, it isn’t part of our list since it is one greater than the product. Therefore, our list is incomplete.

2. If q is not a prime number, then there exists some prime factor that divides into q (this comes from the fundamental theorem of arithmetic). Let’s call this prime factor d.

Suppose d is not a new prime. Suppose it’s on our list of prime numbers, then it would divide nicely into P.

This implies d divides into both P and q.

Since q = P + 1, d must divide into both P and P + 1. Therefore it divides into their difference: (P + 1) – P = 1, as well.

BUT NO PRIME NUMBER DIVIDES ONE — that goes against the definition of a prime number. This is a contradiction to our assumption.

Therefore, we can conclude that d cannot be on our list of primes, and therefore is a new prime number. Hence, our list is incomplete.

In conclusion, we can always find a new prime number not already listed. Therefore, the list of prime numbers is infinite.

QED.

Next Lesson: Can You Solve This Intro Probability Problem?

Other Articles on Euclid’s Work:

The Euclidean Algorithm

Why Does the Euclidean Algorithm Work?

Thanks for reading!

Please click the ❤ to let me know you learned something new!