[proofplan] We argue by contradiction using Euler's analytic idea. If there were only finitely many primes $p_1,\dots,p_k$, then every positive integer would be built from these primes, so each harmonic partial sum would be bounded above by a finite product of geometric series. On the other hand, the harmonic partial sums are unbounded by a direct dyadic grouping argument. These two conclusions are incompatible. [/proofplan] [step:Assume finitely many primes and encode all integers by their prime exponents] Suppose, toward a contradiction, that the set of prime numbers is finite. Let $k \in \mathbb{N}$ be the number of primes, and enumerate them as $p_1,\dots,p_k$. We first record that every $n \in \mathbb{N}$ admits a representation \begin{align*} n = \prod_{i=1}^{k} p_i^{a_i} \end{align*} for some exponents $a_1,\dots,a_k \in \mathbb{N} \cup \{0\}$. Indeed, if some positive integer had no such representation, let $n_0$ be the smallest such integer. Then $n_0 \neq 1$. If $n_0$ were prime, then $n_0 = p_i$ for some $i \in \{1,\dots,k\}$, giving a representation. Hence $n_0$ is composite, so $n_0 = ab$ with $a,b \in \mathbb{N}$ and $1 < a < n_0$, $1 < b < n_0$. By minimality of $n_0$, both $a$ and $b$ have representations using $p_1,\dots,p_k$, and multiplying those representations gives one for $n_0$, a contradiction. [guided] Assume that there are only finitely many primes. Let $k \in \mathbb{N}$ be their number, and list them as $p_1,\dots,p_k$. The analytic estimate below needs the following algebraic input: every positive integer can be written using only the primes in this finite list. We prove this carefully. Suppose the assertion fails, and let $n_0 \in \mathbb{N}$ be the smallest positive integer which cannot be written in the form \begin{align*} n_0 = \prod_{i=1}^{k} p_i^{a_i} \end{align*} with $a_1,\dots,a_k \in \mathbb{N} \cup \{0\}$. The number $1$ has such a representation by taking all $a_i = 0$, so $n_0 \neq 1$. If $n_0$ is prime, then it appears among the complete list of primes, say $n_0 = p_i$, and then the representation is obtained by taking $a_i = 1$ and all other exponents equal to $0$. Therefore $n_0$ cannot be prime. Thus $n_0$ is composite. There exist $a,b \in \mathbb{N}$ such that \begin{align*} n_0 = ab, \qquad 1 < a < n_0, \qquad 1 < b < n_0. \end{align*} By the minimal choice of $n_0$, both $a$ and $b$ have representations in terms of $p_1,\dots,p_k$. Multiplying those two representations gives a representation of $n_0$, contradicting the definition of $n_0$. Hence every positive integer has the claimed representation. [/guided] [/step] [step:Bound every harmonic partial sum by a finite Euler product] For each $N \in \mathbb{N}$, define the $N$th harmonic partial sum \begin{align*} H_N := \sum_{n=1}^{N} \frac{1}{n}. \end{align*} By the representation from the previous step, each term $1/n$ with $1 \leq n \leq N$ is equal to some product $\prod_{i=1}^{k} p_i^{-a_i}$ with $a_i \in \mathbb{N} \cup \{0\}$. Therefore, since all terms are nonnegative, \begin{align*} H_N &\leq \sum_{a_1=0}^{\infty} \cdots \sum_{a_k=0}^{\infty} \prod_{i=1}^{k} p_i^{-a_i} \\ &= \prod_{i=1}^{k} \sum_{a_i=0}^{\infty} p_i^{-a_i} \\ &= \prod_{i=1}^{k} \frac{1}{1 - p_i^{-1}}. \end{align*} The last expression is a finite positive real number because $p_i \geq 2$ for every $i \in \{1,\dots,k\}$. Define \begin{align*} C := \prod_{i=1}^{k} \frac{1}{1 - p_i^{-1}}. \end{align*} Then $H_N \leq C$ for every $N \in \mathbb{N}$. [guided] For each $N \in \mathbb{N}$, define \begin{align*} H_N := \sum_{n=1}^{N} \frac{1}{n}. \end{align*} We want to show that the finite-prime assumption forces all these numbers $H_N$ to stay below one fixed constant. From the previous step, every $n \in \{1,\dots,N\}$ can be written as \begin{align*} n = \prod_{i=1}^{k} p_i^{a_i} \end{align*} for some $a_1,\dots,a_k \in \mathbb{N} \cup \{0\}$. Consequently, \begin{align*} \frac{1}{n} = \prod_{i=1}^{k} p_i^{-a_i}. \end{align*} When we sum over $1 \leq n \leq N$, we get some of the terms appearing in the full $k$-fold geometric sum over all exponent choices. Since every term is nonnegative, enlarging the set of terms can only increase the sum. Hence \begin{align*} H_N &\leq \sum_{a_1=0}^{\infty} \cdots \sum_{a_k=0}^{\infty} \prod_{i=1}^{k} p_i^{-a_i}. \end{align*} The $k$-fold sum factors because the summand is a product of one-variable terms: \begin{align*} \sum_{a_1=0}^{\infty} \cdots \sum_{a_k=0}^{\infty} \prod_{i=1}^{k} p_i^{-a_i} = \prod_{i=1}^{k} \sum_{a_i=0}^{\infty} p_i^{-a_i}. \end{align*} For each prime $p_i$, we have $p_i \geq 2$, so $0 < p_i^{-1} < 1$. The geometric series formula gives \begin{align*} \sum_{a_i=0}^{\infty} p_i^{-a_i} = \frac{1}{1 - p_i^{-1}}. \end{align*} Therefore \begin{align*} H_N \leq \prod_{i=1}^{k} \frac{1}{1 - p_i^{-1}}. \end{align*} Define the constant \begin{align*} C := \prod_{i=1}^{k} \frac{1}{1 - p_i^{-1}}. \end{align*} This is finite because it is a product of finitely many finite positive [real numbers](/page/Real%20Numbers). Thus $H_N \leq C$ for every $N \in \mathbb{N}$. [/guided] [/step] [step:Show the harmonic partial sums are unbounded] For each $m \in \mathbb{N}$, group the terms of $H_{2^m}$ dyadically: \begin{align*} H_{2^m} &= 1 + \sum_{j=0}^{m-1} \sum_{n=2^j+1}^{2^{j+1}} \frac{1}{n}. \end{align*} For each $j \in \{0,\dots,m-1\}$ and each $n \in \{2^j+1,\dots,2^{j+1}\}$, we have $n \leq 2^{j+1}$, hence \begin{align*} \frac{1}{n} \geq \frac{1}{2^{j+1}}. \end{align*} There are $2^j$ integers in the set $\{2^j+1,\dots,2^{j+1}\}$, so \begin{align*} \sum_{n=2^j+1}^{2^{j+1}} \frac{1}{n} \geq 2^j \cdot \frac{1}{2^{j+1}} = \frac{1}{2}. \end{align*} Therefore \begin{align*} H_{2^m} \geq 1 + \frac{m}{2}. \end{align*} Since $1 + m/2$ is unbounded as $m \to \infty$, the sequence $(H_N)_{N \in \mathbb{N}}$ is unbounded. [guided] Now we prove directly that the harmonic partial sums cannot be bounded above. Fix $m \in \mathbb{N}$ and consider the partial sum \begin{align*} H_{2^m} = \sum_{n=1}^{2^m} \frac{1}{n}. \end{align*} We split the terms into dyadic blocks: \begin{align*} H_{2^m} &= 1 + \sum_{j=0}^{m-1} \sum_{n=2^j+1}^{2^{j+1}} \frac{1}{n}. \end{align*} The block indexed by $j$ consists of the integers \begin{align*} 2^j+1,\; 2^j+2,\; \dots,\; 2^{j+1}. \end{align*} There are $2^{j+1} - 2^j = 2^j$ such integers. For every $n$ in this block, we have $n \leq 2^{j+1}$, so taking reciprocals reverses the inequality in the positive real numbers and gives \begin{align*} \frac{1}{n} \geq \frac{1}{2^{j+1}}. \end{align*} Thus the entire block contributes at least \begin{align*} \sum_{n=2^j+1}^{2^{j+1}} \frac{1}{n} \geq 2^j \cdot \frac{1}{2^{j+1}} = \frac{1}{2}. \end{align*} There are $m$ such blocks, one for each $j \in \{0,\dots,m-1\}$. Therefore \begin{align*} H_{2^m} \geq 1 + \frac{m}{2}. \end{align*} As $m$ ranges over $\mathbb{N}$, the quantity $1 + m/2$ has no finite upper bound. Hence the harmonic partial sums $(H_N)_{N \in \mathbb{N}}$ are unbounded. [/guided] [/step] [step:Contradict boundedness and conclude infinitely many primes] The finite-prime assumption gave a constant $C \in \mathbb{R}$ such that $H_N \leq C$ for every $N \in \mathbb{N}$. The dyadic lower bound gives $H_{2^m} \geq 1 + m/2$ for every $m \in \mathbb{N}$. Choose $m \in \mathbb{N}$ such that $1 + m/2 > C$. Then \begin{align*} C \geq H_{2^m} \geq 1 + \frac{m}{2} > C, \end{align*} a contradiction. Therefore the set of prime numbers is infinite. [/step]