# Getting a bound for $\sum \frac{1}{n}$ in terms of a product of a sum of prime reciprocals

I'm trying to prove that $$\sum_{p\text{ prime}}\frac{1}{p}$$ diverges, but I'm stuck on one inequality in the hint (in Rudin) that says: given $N$, let $p_1,\dots, p_k$ be those primes that divide at least one integer $\leq N$. Then: $$\sum_{n=1}^N \frac{1}{n}\leq\prod_{j=1}^k \left(1+\frac{1}{p_j}+\frac{1}{p_j^2}+\dots\right)$$ I can prove the rest after that. I think I have to use the fundamental theorem of arithmetic somehow to decompose the $n\leq N$ into $p_i^{a_i}$ ($i\leq k$) but I'm not entirely sure how. Explicit details would help, as I think I have the idea but I'm failing on the execution.

## 2 Answers

$p_1,...,p_k$ are all of the primes not exceeding $N$. Any $n\leq N$ is a product of non-negative powers of some of $p_1,...,p_k$. Without knowing that prime decompositions are unique, let $p_j^{e_j}$ be the largest power of $p_j$ that doesn't exceed $N$.(That is $p_j^{e_j}\leq N<p_j^{e_j+1})$.When we expand $$P(N)=\prod_{j=1}^{ k} \sum_{i=0}^{ e_j} p_j^{-i}$$ as a sum of reciprocals of positive integers, we see that for $1\leq n\leq N$, the term $1/n$ occurs at least once in the sum. (Unique decomposition implies it occurs exactly once.) There may be other terms,all positive, in the sum, of the form $1/m$ with $m>N$ .Therefore $$P(N)\geq \sum_{n=1}^ {n=N} 1/n.$$

You are close.

The key is that every integer $n \le N$ can be written in the form $n =\prod_{p \in P} p^{a_p(n)}$ where $P$ is the set of primes described above and $a_p(n)$ is the exponent such that $p^{a_p(n)} | n$ and $p^{a_p(n)+1} \not | n$.

Then the product on the right includes all the terms in the sum on the left (and a lot more), so the product is at least as large as the sum.