# Number of Primes is Infinite/Proof 3

## Contents

## Theorem

The number of primes is infinite.

## Proof

Aiming for a contradiction, suppose that there are only $N$ prime numbers.

- $\Bbb P = \left\{{p_1, p_2, \ldots, p_N}\right\}$

By the Fundamental Theorem of Arithmetic, every integer $n > 1$ can be expressed in the form:

- $n = {p_1}^{a_1} {p_2}^{a_2} \dotsm {p_n}^{a_n}$

Let $a$ be the largest of the indices.

Then:

- $\displaystyle \sum_{k \mathop = 1}^n \frac 1 k \le \prod_{j \mathop = 1}^N \left({\sum_{k \mathop = 0}^a \frac 1 { {p_j}^k} }\right)$

expressible in the form:

\((1):\quad\) | \(\displaystyle 1 + \frac 1 2 + \frac 1 3 + \dotsb + \frac 1 n\) | \(\le\) | \(\displaystyle \left({1 + \frac 1 {p_1} + \frac 1 { {p_1}^2} + \dotsb + \frac 1 { {p_1}^n} }\right)\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \) | \(\) | \(\displaystyle +\) | \(\displaystyle \left({1 + \frac 1 {p_2} + \frac 1 { {p_2}^2} + \dotsb + \frac 1 { {p_2}^n} }\right)\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \) | \(\) | \(\displaystyle +\) | \(\displaystyle \ \dotsb\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \) | \(\) | \(\displaystyle +\) | \(\displaystyle \left({1 + \frac 1 {p_N} + \frac 1 { {p_N}^2} + \dotsb + \frac 1 { {p_N}^n} }\right)\) | $\quad$ | $\quad$ |

which can be seen by multiplying out the factors on the right hand side

But from Sum of Infinite Geometric Progression:

- $1 + x + x^2 + \dotsb = \dfrac 1 {1 - x}$

for all $x$ such that $\left\vert{x}\right\vert < 1$.

Thus the factors in $(1)$ are less than the numbers:

- $\dfrac 1 {1 - 1 / p_1}, \dfrac 1 {1 - 1 / p_2}, \dotsb, \dfrac 1 {1 - 1 / p_N}$

and so:

- $1 + \dfrac 1 2 + \dfrac 1 3 + \dotsb + \dfrac 1 n < \dfrac {p_1} {p_1 - 1} \dfrac {p_2} {p_2 - 1} \dotsm \dfrac {p_N} {p_N - 1}$

for every $n$.

This contradicts the result Harmonic Series is Divergent.

Hence the result, by Proof by Contradiction.

$\blacksquare$

## Historical Note

This proof was devised by Leonhard Paul Euler.

## Sources

- 1972: George F. Simmons:
*Differential Equations*... (previous) ... (next): $\S 3$: Appendix $\text A$: Euler