[proofplan]
We argue by contradiction using Euler's product idea in a finite form. For a finite set of primes $S$, unique factorisation identifies the product of the geometric series $\prod_{p \in S}(1 - 1/p)^{-1}$ with the sum of $1/n$ over integers whose prime divisors lie in $S$. If all primes were contained in one finite set $P$, this finite product would equal the harmonic series, but the harmonic series diverges.
[/proofplan]
[step:Expand the Euler product over a finite set of primes]
Let $P$ denote the set of prime numbers, and let $S \subset P$ be a finite subset. Define $N_S \subset \mathbb{Z}_{\geq 1}$ by
\begin{align*}
N_S := \left\{ n \in \mathbb{Z}_{\geq 1} : \text{every prime divisor of } n \text{ belongs to } S \right\}.
\end{align*}
For each $p \in S$, the geometric series formula gives
\begin{align*}
\left(1 - \frac{1}{p}\right)^{-1} = \sum_{k=0}^{\infty} \frac{1}{p^k},
\end{align*}
because $0 < 1/p < 1$. Since $S$ is finite and each geometric series is absolutely convergent, finite distributivity for absolutely convergent series gives
\begin{align*}
\prod_{p \in S} \left(1 - \frac{1}{p}\right)^{-1}
&= \prod_{p \in S} \sum_{k=0}^{\infty} \frac{1}{p^k} \\
&= \sum_{(k_p)_{p \in S} \in \mathbb{Z}_{\geq 0}^S} \prod_{p \in S} \frac{1}{p^{k_p}}.
\end{align*}
Define the map
\begin{align*}
A_S: \mathbb{Z}_{\geq 0}^S &\to N_S \\
(k_p)_{p \in S} &\mapsto \prod_{p \in S} p^{k_p}.
\end{align*}
By the [Fundamental Theorem of Arithmetic](/theorems/723), $A_S$ is a bijection. Therefore
\begin{align*}
\prod_{p \in S} \left(1 - \frac{1}{p}\right)^{-1}
= \sum_{n \in N_S} \frac{1}{n}.
\end{align*}
[guided]
The purpose of this step is to make Euler's product precise without using an infinite product. Let $P$ be the set of prime numbers, and let $S \subset P$ be finite. We define
\begin{align*}
N_S := \left\{ n \in \mathbb{Z}_{\geq 1} : \text{every prime divisor of } n \text{ belongs to } S \right\}.
\end{align*}
This is the set of positive integers that can be built using only primes from $S$.
For each $p \in S$, we have $p \geq 2$, hence $0 < 1/p < 1$. The geometric series formula applies and gives
\begin{align*}
\left(1 - \frac{1}{p}\right)^{-1} = \sum_{k=0}^{\infty} \frac{1}{p^k}.
\end{align*}
Because $S$ is finite and all these geometric series are absolutely convergent, we may multiply them and distribute terms:
\begin{align*}
\prod_{p \in S} \left(1 - \frac{1}{p}\right)^{-1}
&= \prod_{p \in S} \sum_{k=0}^{\infty} \frac{1}{p^k} \\
&= \sum_{(k_p)_{p \in S} \in \mathbb{Z}_{\geq 0}^S} \prod_{p \in S} \frac{1}{p^{k_p}}.
\end{align*}
Here $\mathbb{Z}_{\geq 0}^S$ denotes the set of tuples $(k_p)_{p \in S}$ of non-negative integers indexed by the primes in $S$.
Now define
\begin{align*}
A_S: \mathbb{Z}_{\geq 0}^S &\to N_S \\
(k_p)_{p \in S} &\mapsto \prod_{p \in S} p^{k_p}.
\end{align*}
The [Fundamental Theorem of Arithmetic](/theorems/730) says that every positive integer has a unique prime factorisation. Therefore every tuple $(k_p)_{p \in S}$ gives one integer in $N_S$, and every integer in $N_S$ arises from exactly one such tuple. Thus $A_S$ is a bijection. Reindexing the previous sum through this bijection yields
\begin{align*}
\prod_{p \in S} \left(1 - \frac{1}{p}\right)^{-1}
= \sum_{n \in N_S} \frac{1}{n}.
\end{align*}
[/guided]
[/step]
[step:Show that finitely many primes would make the harmonic series finite]
Assume for contradiction that $P$ is finite. Applying the previous step with $S = P$, the Fundamental Theorem of Arithmetic gives $N_P = \mathbb{Z}_{\geq 1}$. Hence
\begin{align*}
\sum_{n=1}^{\infty} \frac{1}{n}
= \sum_{n \in N_P} \frac{1}{n}
= \prod_{p \in P} \left(1 - \frac{1}{p}\right)^{-1}.
\end{align*}
The product on the right is finite, because $P$ is finite and each factor satisfies
\begin{align*}
1 < \left(1 - \frac{1}{p}\right)^{-1} < \infty.
\end{align*}
Therefore the assumption that $P$ is finite implies
\begin{align*}
\sum_{n=1}^{\infty} \frac{1}{n} < \infty.
\end{align*}
[/step]
[step:Prove that the harmonic series diverges by dyadic grouping]
For each $K \in \mathbb{Z}_{\geq 0}$, group the partial sum through $2^{K+1}-1$ into dyadic blocks:
\begin{align*}
\sum_{n=1}^{2^{K+1}-1} \frac{1}{n}
= \sum_{k=0}^{K} \sum_{n=2^k}^{2^{k+1}-1} \frac{1}{n}.
\end{align*}
For fixed $k \in \{0,\dots,K\}$ and every $n \in \{2^k,\dots,2^{k+1}-1\}$, we have $n \leq 2^{k+1}-1 < 2^{k+1}$, so
\begin{align*}
\frac{1}{n} > \frac{1}{2^{k+1}}.
\end{align*}
There are $2^k$ integers in the block. Hence
\begin{align*}
\sum_{n=2^k}^{2^{k+1}-1} \frac{1}{n}
\geq \sum_{n=2^k}^{2^{k+1}-1} \frac{1}{2^{k+1}}
= \frac{2^k}{2^{k+1}}
= \frac{1}{2}.
\end{align*}
Therefore
\begin{align*}
\sum_{n=1}^{2^{K+1}-1} \frac{1}{n}
\geq \sum_{k=0}^{K} \frac{1}{2}
= \frac{K+1}{2}.
\end{align*}
Since $(K+1)/2 \to \infty$ as $K \to \infty$, the harmonic series diverges:
\begin{align*}
\sum_{n=1}^{\infty} \frac{1}{n} = +\infty.
\end{align*}
[/step]
[step:Contradict the finiteness conclusion and conclude infinitely many primes]
The assumption that $P$ is finite implies
\begin{align*}
\sum_{n=1}^{\infty} \frac{1}{n} < \infty,
\end{align*}
while the dyadic grouping argument proves
\begin{align*}
\sum_{n=1}^{\infty} \frac{1}{n} = +\infty.
\end{align*}
This contradiction shows that $P$ is not finite. Therefore there are infinitely many prime numbers.
[/step]
