# Formal Proof of the Infinitude of Primes

In the Infinitude of Primes post, we have shown intuitively that there are infinitely many primes. In this post, we use our intuitive proof to create a more formal proof. The proof was supposedly constructed by Euclid and was shown in his book, The Elements.

We are going to use the proof strategy called proof by contradiction. Our proof is summarized as follows:

1.)  We assume that the opposite of our conjecture is true.

2.) From our assumption, deduce by logical arguments, and find a contradiction somewhere.

3.)  Conclude that if our assumption has a contradiction, then our conjecture must be true.

Conjecture: There are infinitely many primes.

Proof:

1.)    We assume that the opposite of our conjecture is true. Suppose there is a finite number primes. Assuming that there are only n of them, namely p1, p2, p3, …, pn.

2.)    Let S be the set of all primes. Then S = {p1, p2, p3 ,…, pn}. Let N be the product of all primes added to 1.  It follows that N =  p1 p2 p3pn + 1.

Now, we know that N can either be prime  or composite.  On the one hand, if N is prime, then we found another prime number not in S. This contradicts our assumption that there are only n primes.

On the other hand, if N is composite, dividing it by any prime (or product of primes) in set S will leave a remainder of 1. Since N is composite, it must be a product of primes. This means that at least one of its factors is a prime not in S. In effect, we found another prime number not in set S. Again, this contradicts our assumption that there are only n primes.

3.)    In any case, we found another prime not in S.  Both contradict the assumption that there are only n primes. As a consequence, our assumption is false, which means that our conjecture is true.

The arguments above show that given any finite set of primes, we can always find a prime not on that set.

Therefore, there are infinitely many primes.