Problem

Prove that there are infinitely many prime numbers.

Solution

The proof by contradiction is the most elegant way to show that there are infinitely many prime numbers. Assume that there are only finitely many prime numbers. Then we can list them out: p_1, p_2, ..., p_n. Consider the number N = p_1p_2...p_n + 1. N is clearly greater than 1 and is not divisible by any of the primes p_i, so N must be prime. This contradicts the assumption that there are only finitely many primes, so therefore there must be infinitely many primes.