Note: This is the third part of the Prime Number Series

- Part I: Introduction to Prime Numbers
- Part III: Formal Proof of the Infinitude of Prime Numbers

In Introduction to Prime Numbers, we conjectured that the number of prime numbers is decreasing as the counting numbers increase. In this post, we discuss intuitively that there is no greatest prime, or that there are infinitely many prime numbers.

Before proceeding with our discussion, it is noteworthy to remember that a number can either be prime or composite. We also know that composite numbers are product of primes.

Many people know Euclid for his work in geometry, but only a few know about his work in number theory. In Book IX of *The Elements*, Euclid proved that there infinitely many prime numbers. The discussion below is an intuitive explanation of his proof.

Let us have the following analogy:

**Assuming that the only primes that exist are in S = {2,3,5}**. We multiply all the primes in**S**and then add 1: (2x3x5 +1) = 31.- If 31 is prime (in fact, it is) then our assumption that
**(1)**is false because we found another prime not in**S**. - We can probably be skeptical and say, hmmm… maybe {2,3,5,31} are the only primes. Again, we multiply all the numbers in the set and add 1: 2 x 3 x 5 x 31 + 1 = 931. Is 931 prime? No. 931 = (19)(7)(7). Note that 19 and 7 are primes and not in
**S**. Again, we found primes not in set**S**.

Let us summarize the steps that we have done to look for primes.

- We multiplied all the primes in set
**S**then added 1. - If the result is prime, we found another prime not in
**S**. - If the result is composite, then it must be a product of primes. Since dividing it with any of the factors in
**S**will give a remainder 1 (Why?), this implies that at least one of its factors is a prime not in**S**. Still, we found another prime not in**S**.

Now, steps 1-3 can go on forever because once we found a prime not in **S**, we can always include it in **S** and repeat the process. For example, we can say maybe {2, 3, 5, 7, 19, 31} are the only primes and we proceed to 2 and 3.

Since it is possible to repeat the process infinitely,

Given a finite list of primes, we can always find primes not on that list.

Hence, there are infinitely many primes.

In the next post in the series, we prove formally the discussion above.