# An Intuitive Proof to The Infinitude of Primes

Introduction

Prime numbers are numbers with only two factors, $1$ and itself. Eleven is prime since its factors are only $1$ and $11$. Numbers that are not prime are called composite. Fifteen is composite because it has more than $2$ factors. The factors of $15$ are $1$, $3$, $5$, and $15$.

White squares show primes from 1 to 100 (via mathandmultimedia.com).

As you count farther, you will observe that the number of primes are getting fewer and fewer. There are $168$ primes between $1$ and $1000$, $135$ primes between $1000$ and $2000$, $127$ primes between $2000$ and $3000$, and $120$ primes between $3000$ and $4000$. Now, the question is, “Is there a largest prime?” The equivalent to this question is, “Are the number of primes finite?” In this post, we are going to prove intuitively that the number of primes is infinitely many.

The Proof

Theorem: There are infinitely many primes.

Proof:

We can prove that there are infinitely prime numbers if we can show that given any finite list of primes, we can always find a new prime not on that list. We will only start with cases, but this is enough for the proof.  We will discuss the generalization of the proof with algebraic symbols in a different post.

1. Suppose that there are only a finite number of primes and it is contain in the set $S_1 = \{2, 3, 5 \}$. If we multiply all the numbers in the set and add 1, we have  $(2 \times 3 \times 5 + 1 = 31)$, the product can be prime or composite.
2. Verifying 31, we see that its is a prime. So, we found a prime not in $S_1$.
3. Well, maybe $S_2 =\{ 2, 3, 5, 31 \}$ are the only primes. Repeating the process, we have $2 \times 3 \times 5 \times 31 + 1 = 931$.
4. Now, $937$ is composite since $931 = 19(7)(7)$. Now, we can see that $19$ and $7$ are primes, but they are not on the list.
5. Note that the process above can be repeated infinitely.

Why the Proof Above Works

In the case above, we have shown that given a finite list of primes, we can always find a prime not on that list. By multiplying all the numbers on the list, you can have two cases: the product can be prime or composite.

Case 1: The product is prime.

If the product of all the numbers added to 1 is prime, then the product is a prime number not on the list. Therefore, we found another prime not on the list.

Case 2: The product is composite.

If the product of all the numbers added to 1 is composite, then it must be a product of primes. But the product gives a remainder of 1 if you divide it with any of the factors (Why?). Therefore, one of its factors is a prime not on the list. Again, we found another prime not on the list.

Conclusion. As we can see, in either case, given a finite list of prime, we can always find a prime not on the list. Therefore, there are infinitely many primes.

## 4 thoughts on “An Intuitive Proof to The Infinitude of Primes”

1. In steps 3 and 4 of the proof, “937” should be “931”. Also, in step 3, a “+1” is missing in the last equation.