# 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 ProofOfInfinitudeOfPrimes 2013-12-27 17:11:49 2013-12-27 17:11:49 rspuzio (6075) rspuzio (6075) 15 rspuzio (6075) Proof msc 11A41