How Do We Know Prime Numbers are Infinite?

  • by Brett Berry - Sun, 02/12/2017 - 22:33

 

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.

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.