We begin by noting a fact about factorizations. Suppose that $n > 0$ is an integer which has a prime factorization$$ n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} .$$ Then, because $2$ is the smallest prime number, we must have$$ p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} \ge 2^{k_1} 2^{k_2} \cdots 2^{k_m},$$ so $n \ge 2^{k_1 + k_2 + \cdots + k_m}$ .

Assume that there were only a finite number of prime numbers $p_1, p_2, \ldots p_m$ . By the above-noted fact, given an integer $j > 0$ , every integer $n > 0$ could be expressed as$$ n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$$ with$$ k_1 + k_2 + \cdots + k_m \le j .$$

This, however, leads to a contradiction because it would imply that there exist more integers than possible factorizations despite the fact that every integer is supposed to have a prime factorization. To see this, let us over-count the number of factorizations. A factorization being specified by an $m$ -tuplet of integers $k_1, k_2, \ldots, k_n$ such that $k_1 + k_2 + \cdots + k_m \le j$ , the number of factorizations is equal to the number of such tuplets. Now, for all $i$ we must have $0 \le k_i \le j$ , so there are not more than $(j+1)^m$ such tuplets available. However, for all $m$ , one can choose $j$ such that $2^j > (j+1)^m$ . For such a choice of $j$ we could not make ends meet -- there are not enough possible factorizations available to handle all integers, so we conclude that there must be more than $m$ primes for any integer $m$ , i.e. that the number of primes is infinite.

To make this exposition self-contained, we conclude with a proof that, for every $m$ , there exists a $j$ such that $2^j > (j+1)^m$ . We begin with the case $m=1$ and showing that, for every integer $a \ge 2$ , we have $2^a > a+1$ . This is an easy induction. When $a = 2$ , we have $2^2 = 4 > 3 = 2 + 1$ . If $2^a > a+1$ for some $a > 2$ , then $2^a + 1 > a + 2$ . By our hypothesis, $2^a \ge 1$ , so $2^a + 1 \ge 2^a + 2^a = 2^{a+1}$ , hence $2^{a+1} > (a+1)+1$ .

From this starting point, we obtain the desired inequality by algebraic manipulation. Setting $a = m - 1$ , we have $2^{m-1} > m$ , or $2^m > 2 m$ . Raising both sides to the $2m$ -th power, $2^{2 m^2} > 2^{2m} m^{2m} = 2^m (2 m^2)^m \ge 2 (2 m^2)^m$ . Setting $j = (2 m^2 - 1)$ , this becomes $2^j > (j+1)^2$ .