## You are here

Homeproof of infinitude of primes

## Primary tabs

# 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}$.

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections