PlanetMath: proof of infinitude of primes

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of infinitude of primes

(Proof)

We begin by noting a fact about factorizations. Suppose that is an integer which has a prime factorization

$\displaystyle n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} .$

Then, because

is the smallest prime number, we must have

$\displaystyle 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 , every integer could be expressed as

$\displaystyle n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$

with

$\displaystyle 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 -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 we must have $0 \le k_i \le j$ , 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 $a \ge 2$ , we have . This is an easy induction. When , we have . If for some , then . 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 , we have $2^{m-1} > m$ , or . Raising both sides to the -th power, $2^{2 m^2} > 2^{2m} m^{2m} = 2^m (2 m^2)^m \ge 2 (2 m^2)^m$ . Setting , this becomes .