| Version current |
Version 2 |
| We begin by noting a fact about factorizations. Suppose that $n > 0$ is an integer |
We begin by noting a fact about factorizations. Suppose that $n > 0$ is an integer |
| which has a prime factorization |
which has a prime factorization |
| \[ |
\[ |
| n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} . |
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 |
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 |
p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} \ge |
| 2^{k_1} 2^{k_2} \cdots 2^{k_m}, |
2^{k_1} 2^{k_2} \cdots 2^{k_m}, |
| \] |
\] |
| so $n \ge 2^{k_1 + k_2 + \cdots + 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$. |
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 |
By the above-noted fact, given an integer $j > 0$, every integer $n > 0$ could be |
| expressed as |
expressed as |
| \[ |
\[ |
| n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} |
n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} |
| \] |
\] |
| with |
with |
| \[ |
\[ |
| k_1 + k_2 + \cdots + k_m \le j . |
k_1 + k_2 + \cdots + k_m \le j . |
| \] |
\] |
|
|
| This, however, leads to a contradiction because it would imply that there exist more |
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 |
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 |
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 |
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 |
$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 |
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. |
$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 |
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 |
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 |
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. |
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$. |
|
