## 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.