Counting Primes

This is a classic problem first solved by Euclid: Show that there are infinitely many prime numbers.

This is a classic example usually used in introducing proofs by contradiction.

Assume by way of contradiction that there are finitely many primes, then we can order all primes by their value.

Here, each of are primes, and by the assumption that the number of primes is finite, let’s arbitrarily say that there are exactly primes.

Now, consider the number , by the nature of the naturals, can either be prime or composite.

Suppose that is prime, then because , this means that is larger than and hence cannot be any of the primes ordered above. This then violates the claim that there are only primes.

Therefore, it can only be the case that is composite. Since all primes are already listed, then there must exist some prime number such that

Because 1 isn’t a prime, this violates the claim that is prime. Therefore, it cannot be the case that the assumption that there are finite number of primes.

Woosh