|
We begin by noting a fact about factorizations. Suppose that is an integer which has a prime factorization
Then, because is the smallest prime number, we must have
so
.
Assume that there were only a finite number of prime numbers
. By the above-noted fact, given an integer , every integer could be expressed as
with
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 -tuplet of integers
such that
, the number of factorizations is equal to the number of such tuplets. Now, for all we must have
, so there are not more than such tuplets available. However, for all , one can choose such that
. For such a choice of 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 primes for any integer , i.e. that the number of primes is infinite.
To make this exposition self-contained, we conclude with a proof that, for every , there exists a such that
. We begin with the case and showing that, for every integer , we have . This is an easy induction. When , we have
. If for some , then
. By our hypothesis, , so
, hence
.
From this starting point, we obtain the desired inequality by algebraic manipulation. Setting , we have
, or . Raising both sides to the -th power,
. Setting
, this becomes
.
|