# 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}}\mathrm{\cdots}{p}_{m}^{{k}_{m}}.$$ |

Then, because $2$ is the smallest prime number^{}, we must have

$${p}_{1}^{{k}_{1}}{p}_{2}^{{k}_{2}}\mathrm{\cdots}{p}_{m}^{{k}_{m}}\ge {2}^{{k}_{1}}{2}^{{k}_{2}}\mathrm{\cdots}{2}^{{k}_{m}}={2}^{{k}_{1}+{k}_{2}+\mathrm{\cdots}+{k}_{m}},$$ |

so $n\ge {2}^{{k}_{1}+{k}_{2}+\mathrm{\cdots}+{k}_{m}}$.

Assume that there were only a finite number of prime numbers ${p}_{1},{p}_{2},\mathrm{\dots}{p}_{m}$. By the above-noted fact, given a positive integer $j$, every integer n such that ${2}^{j}\ge n>0$ could be expressed as

$$n={p}_{1}^{{k}_{1}}{p}_{2}^{{k}_{2}}\mathrm{\cdots}{p}_{m}^{{k}_{m}}$$ |

with

$${k}_{1}+{k}_{2}+\mathrm{\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 $m$-tuplet of integers
${k}_{1},{k}_{2},\mathrm{\dots},{k}_{n}$ such that ${k}_{1}+{k}_{2}+\mathrm{\cdots}+{k}_{m}\le j$, the number of
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.
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\ge 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\ge 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}^{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}$.

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 |