The Infinitude of Primes

We use proof by contradiction, combined with the Fundamental Theorem of Arithmetic (existence part: every integer greater than $1$ has at least one prime divisor). Step 1 (Existence of a prime factor). First we record the elementary fact, itself a consequence of well-ordering, that every integer $n > 1$ has a prime divisor. Indeed, let $S$ be the set of divisors of $n$ that are greater than $1$; $S$ is nonempty since $n \in S$. By the well-ordering principle, $S$ has a least element $d$. We claim $d$ is prime. If not, $d = ab$ with $1 < a, b < d$; but then $a$ is a divisor of $n$ (since $a \mid d \mid n$) with $1 < a < d$, contradicting minimality of $d$ in $S$. Hence $d$ is prime and $d \mid n$. Step 2 (Suppose finitely many primes). Suppose, for contradiction, that there are only finitely many primes in total, say exactly

for some $k \geq 1$ (the case $k=0$, no primes at all, is immediately impossible since $2$ is prime by definition, so we may assume $k \geq 1$). Step 3 (Construct $N$). Define

Since each $p_i \geq 2$, we have $N \geq 2\cdot 1 + 1 = 3 > 1$ (more precisely $N \ge p_1+1\ge 3$), so by Step 1, $N$ has at least one prime divisor $q$. Step 4 ($q$ is not any $p_i$). We claim $q \neq p_i$ for every $i = 1, \dots, k$. Suppose toward contradiction that $q = p_i$ for some $i$. Since $q \mid N$, we have $q \mid \left(p_1 p_2 \cdots p_k + 1\right)$. Also $q = p_i$ clearly divides the product $p_1 p_2 \cdots p_k$ (it is one of the factors). Therefore $q$ divides the difference

But no prime divides $1$, since the only divisors of $1$ are $1$ itself, and a prime is by definition greater than $1$. This is a contradiction. Step 5 (Conclusion). Hence $q$ is a prime not equal to any of $p_1, \dots, p_k$. This contradicts our assumption in Step 2 that $p_1,\dots,p_k$ is the complete list of all primes. Therefore the assumption of Step 2 is false: there cannot be only finitely many primes. Since the set of primes is not finite, and it is a subset of the positive integers, it must be (countably) infinite. $\blacksquare$ (Remark on the second formulation.) The argument in fact proves the stronger, constructive statement: given any finite set of primes $\{p_1,\dots,p_k\}$ — not necessarily "all primes so far" — the number $N = p_1\cdots p_k + 1$ has a prime factor outside the set. This is exactly Steps 3–4 above, without needing Step 2's contradiction framing; the contradiction form is only needed to convert "arbitrary finite set has a prime outside it" into "the set of all primes is infinite." Both formulations are equivalent and both are established by the proof above.

This is Euler's proof, using analytic estimates and the Fundamental Theorem of Arithmetic; it is logically independent of Euclid's combinatorial argument and gives a quantitatively stronger conclusion. Step 1 (Euler product, finite truncation). Fix $x \ge 2$ and let $p_1 < p_2 < \cdots < p_k$ be all the primes $\le x$ (there are only finitely many integers $\le x$, hence finitely many primes $\le x$, regardless of whether $\mathbb P$ itself is finite or infinite). For each prime $p_i$ and any integer $m \ge 1$,

a convergent geometric series since $1/p_i < 1$. Consider the finite product

Expanding this product of absolutely convergent series, every term is of the form $\frac{1}{p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k}}$ for nonnegative integers $a_1,\dots,a_k$. By the Fundamental Theorem of Arithmetic (uniqueness of factorization), as $(a_1,\dots,a_k)$ ranges over all nonnegative integer tuples, the numbers $n = p_1^{a_1}\cdots p_k^{a_k}$ range over exactly the set of positive integers whose prime factors all lie among $p_1,\dots,p_k$ — each such $n$ arising from exactly one tuple. In particular, every integer $n$ with $1 \le n \le x$ has all its prime factors $\le x$ (since any prime factor of $n$ is at most $n \le x$), hence all its prime factors among $p_1,\dots,p_k$. Therefore

Step 2 (Harmonic series diverges). The harmonic series $\sum_{n=1}^{M} 1/n$ diverges as $M \to \infty$; concretely, grouping terms in blocks of doubling length,

which is unbounded as $r \to \infty$ (each block $\frac{1}{2^{s}+1} + \cdots + \frac{1}{2^{s+1}}$ has $2^s$ terms each $\ge 1/2^{s+1}$, summing to $\ge 1/2$). Hence the right side of Step 1's inequality tends to $\infty$ as $x \to \infty$, so

Step 3 (From the product to the sum of reciprocals). Using $\log(1-t)^{-1} = t + t^2/2 + t^3/3+\cdots \le t + t^2$ for $0 \le t \le 1/2$ (valid since $p\ge 2 \Rightarrow t = 1/p \le 1/2$, and the tail $\sum_{j\ge 2} t^j/j \le \sum_{j\ge2} t^j = t^2/(1-t) \le t^2$ when $t\le 1/2$), we get for each prime $p \le x$:

Summing over primes $p \le x$ and taking logarithms of Step 2's divergent product,

while $\sum_{p} \frac{1}{p^2} \le \sum_{n=2}^\infty \frac{1}{n^2} < \infty$ converges (comparison to a convergent $p$-series-type bound), contributing a bounded amount. Therefore

Step 4 (Conclusion). If there were only finitely many primes in total, the sum $\sum_{p\le x} 1/p$ would be bounded above (by the finite total sum $\sum_{\text{all } p} 1/p$) for all $x$, contradicting Step 3's divergence. Hence there are infinitely many primes. $\blacksquare$

This is a combinatorial variant, due essentially to Goldbach, using a telescoping identity rather than a direct contradiction. Step 1 (Telescoping identity). We claim that for all $n \ge 1$,

We prove this by induction on $n$. Base case $n=1$: $F_0 = 2^{2^0}+1 = 3$, and $F_1 - 2 = (2^{2^1}+1) - 2 = 5 - 2 = 3$. Equal, so the base case holds. Inductive step: suppose $F_0F_1\cdots F_{n-1} = F_n - 2$ for some $n \ge 1$. Then

Now compute $F_{n+1} - 2 = 2^{2^{n+1}} - 1 = \left(2^{2^n}\right)^2 - 1$. Writing $t = 2^{2^n}$, so $F_n = t+1$, we have $F_{n+1} - 2 = t^2 - 1 = (t+1)(t-1) = F_n(F_n - 2) = F_n^2 - 2F_n$. This matches the expression above, completing the induction. Step 2 (Pairwise coprimality). Let $0 \le m < n$. By Step 1, $F_n - 2 = F_0 F_1 \cdots F_{n-1}$, and since $m < n$, $F_m$ appears as one of the factors on the right side, so $F_m \mid (F_n - 2)$. Suppose $d$ is a common divisor of $F_m$ and $F_n$; then $d \mid F_n$ and $d \mid F_n - 2$ implies $d \mid \big(F_n - (F_n-2)\big) = 2$. So $d \in \{1,2\}$. But every $F_k = 2^{2^k}+1$ is odd (as $2^{2^k}$ is even for $k\ge 0$, since $2^k \ge 1$, and even$+1=$odd), so $2 \nmid F_k$. Hence $d = 1$: $\gcd(F_m, F_n) = 1$. Step 3 (Infinitude of primes). Each $F_n \ge F_0 = 3 > 1$, so by the existence-of-prime-factor fact (Step 1 of Euclid's proof above), each $F_n$ has at least one prime factor $q_n$. Since the $F_n$ are pairwise coprime by Step 2, no prime can divide two different $F_n$'s: if $r \mid F_m$ and $r \mid F_n$ with $m\ne n$, then $r \mid \gcd(F_m,F_n)=1$, impossible for a prime $r$. Hence the primes $q_0, q_1, q_2, \dots$ are pairwise distinct, giving an infinite sequence of distinct primes, one for each $n = 0,1,2,\dots$. Therefore there are infinitely many primes. $\blacksquare$