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:

  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.