proof of infinitude of primes

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}}\geq 2^{k_{1}}2^{k_{2}}\cdots 2^% {k_{m}}=2^{k_{1}+k_{2}+\cdots+k_{m}},

so $n\geq 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 a positive integer $j$ , every integer n such that $2^{j}\geq 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}\leq 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}\leq j$ , the number of factorizations is equal to the number of such tuplets. Now, for all $i$ we must have $0\leq k_{i}\leq 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^{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 by showing that, for every integer $a\geq 1$ , we have $2^{a}>a$ . This is an easy induction. When $a=1$ , we have $2^{1}=2>1$ . If $2^{a}>a$ for some $a>1$ , then $2^{a+1}=2^{a}+2^{a}>a+a>a+1$ . Hence, by induction, $2^{a}>a$ for all $a\geq 1$ .

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

Title	proof of infinitude of primes
Canonical name	ProofOfInfinitudeOfPrimes
Date of creation	2013-12-27 17:11:49
Last modified on	2013-12-27 17:11:49
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	15
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 11A41