In the Infinitude of Primes post, we have shown intuitively that there are infinitely many primes. In this post, we are going to use our intuitive proof to create a more formal proof. The proof was supposedly constructed by Euclidand 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 p₁, p₂,p₃, …, p_n.

2.)    Let S be the set of all primes. Then S = {p₁, p₂, p₃ ,…, p_n}. Let N be the product of all primes added to 1.  It follows that N =  p₁ p₂ p₃ … p_n + 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 contradictsour assumption that there are only n primes.

On the other hand, ifN is composite, dividing it by any prime (or product of primes) from 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.Again, we found another prime number not in set S. Again, this contradicts ourassumption that there are only n primes.

3.)    In any case, we found another prime not in S.  Both contradict our 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.