Add Me!Close Menu Navigation

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.

    \[p_1 < p_2 < \stackrel{k}{\ldots} < p_{k-1} < p_k\]

Here, each of p_i \in \mathbb{N} are primes, and by the assumption that the number of primes is finite, let’s arbitrarily say that there are exactly k primes.

Now, consider the number P = p_1 \times \stackrel{k}{\dots} \times p_k + 1, by the nature of the naturals, P can either be prime or composite.

Suppose that P is prime, then because p_k < p_1 \times \stackrel{k}{\dots} \times p_k < P, this means that P is larger than p_k and hence cannot be any of the k primes p_i ordered above. This then violates the claim that there are only k primes.

Therefore, it can only be the case that P is composite. Since all primes are already listed, then there must exist some prime number p_n \in \{p_1 \ldots p_k\} such that p_n | P

    \begin{align*} p_n|(p_1 \times \cdots p_n \times \cdots p_k + 1) &\implies p_n|1 \\ &\iff p_n = 1 \end{align*}

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

Posted By Lee

Woosh

Recent Comments