Solution

Prove that there are infinitely many prime numbers.


Let's try to argue by contradiction...

Assume that there are only a finite number of primes.

Under this assumption, we can let $n$ denote the number of primes, and list them all in the following way: $$p_1, p_2, p_3, \ldots, p_n$$ Now consider the number $$q = p_1 p_2 p_3 \ldots p_n + 1$$ Clearly, $q$ is larger than the largest prime, so it can't be prime itself. Thus, some prime must divide $q$. Without loss of generality, suppose $p_1 \mid q$. But then,
$$\begin{align}p_1 \mid p_1 p_2 p_3 \ldots p_n + 1 &\Rightarrow p_1 p_2 p_3 \ldots p_n + 1 = p_1 k \quad \textrm{for some integer $k$}\\
&\Rightarrow 1 = p_1 k - p_1 p_2 p_3 \ldots p_n\\
&\Rightarrow 1 = p_1(k - p_2 p_3 \ldots p_n)\\
&\Rightarrow p_1 \mid 1\end{align}$$ But no prime can divide 1!   This gives us the contradiction we need.

Our assumption must be rejected, and the opposite must be true:

There are infinitely many primes.

QED.