# Proof: There are infinitely many primes

## by Subhomoy Haldar

# Theorem

There are infinitely many primes.

# Proof by Contradiction

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:

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