# Theorem

There are infinitely many primes.

Suppose the opposite is true, that is, there are only finitely many primes. Let all of them be contained in the set $P$ and the number of primes be $k$.

We proceed to enumerate all the elements of this set, the primes, as:

$$p_1, p_2, \ldots, p_k$$

Now, we define another number $p$ in the following manner

$$p = \prod_{i=1}^{k}{p_i} + 1$$

If we assume that $p$ is prime, then it is larger than any of the elements in $P$, so it is not contained in $P$. The statement that $P$ was a complete set of primes is, therefore, wrong.

If we assume that $p$ is composite, then there must be a prime factor $p'$ that divides $p$. Now

$$p' \mid\prod_{i=1}^{k}{p_i},$$

because all primes are included in the product. So it must be true that

$$p' \mid\left(p-\prod_{i=1}^{k}{p_i}\right)$$ $$\text{or, } p' \mid 1$$

Since no prime can divide $1$, it must not be a member of $P$, suggesting that the list of primes is incomplete.

In either case, our assumption is wrong. Hence, there are infinitely many primes.

## Q.E.D.

This proof is due to Euclid.

# Spot an Error?

Contact me with the details. I’ll update the post at the earliest. Make sure to include the following details:

1. Post name - and the link too.
2. The type of error - typographical error or conceptual or anything else.
3. Suggested fix - if you can supply it, the update will be quicker.