# Thread: Erdos proof Sum of Reciprocals of Primes

1. ## Erdos proof Sum of Reciprocals of Primes

I've been going through the Erdos proof that the sum of the reciprocals of primes is divergent. I'm having trouble understanding why there are 2^k possible ways to write the square free part.

2. Originally Posted by grandunification
I've been going through the Erdos proof that the sum of the reciprocals of primes is divergent. I'm having trouble understanding why there are 2^k possible ways to write the square free part.
Well, the set of squarefree natural numbers having all of their prime divisors in the set $\{p_1, \dots, p_k\}$ is in bijective correspondence with the collection of subsets of $\{p_1, \dots, p_k\}$; and this collection has $2^k$ elements.

3. Yes, but I don't see why we should include the empty set in counting. So I think it should be 2^k-1. Is it because in n =rm^2 we need to also throw in the possibility that no prime occurs in the factorization of r because r = 1? Also, I would like to see a proof that n can always be written as rm^2. That's not clear to me.

4. Originally Posted by grandunification
Yes, but I don't see why we should include the empty set in counting. So I think it should be 2^k-1. Is it because in n =rm^2 we need to also throw in the possibility that no prime occurs in the factorization of r because r = 1? Also, I would like to see a proof that n can always be written as rm^2. That's not clear to me.
The empty set corresponds to the empty product, which is equal to $1$.

As for representation of integers as the product of a squarefree integer and a square : Suppose $n=p_1^{a_1}\dots p_k^{a_k}$ is the canonical representation of $n$ as a product of prime-powers. Using the division algorithm, write $a_j = 2q_j+r_j$, $0\leq r_j <2$, for $j=1,\dots,k$. Then $n=rm^2$, where $r=p_1^{r_1}\dots p_k^{r_k}$ is squarefree and $m=p_1^{q_1}\dots p_k^{q_k}$. I'll let you show that this representation is unique.

If you know a bit about algebra, we can state this situation in more abstract terms. Consider $(\mathbb{N}, \times)$ (excluding $0$) as a commutative monoid. The set of $u^{th}$ powers $S_u=\{j^u : j \in \mathbb{N}\}$ is a sub-monoid, and the quotient monoid $\mathbb{N}/S_u$ is isomorphic to to $(\mathbb{Z}/u\mathbb{Z})^\mathbb{N}$ (this is actually a group, since every element in this monoid has finite order at most $u$). In the case $u=2$, which is your case, the monoid $\mathbb{N}/S_2$ can in fact be considered as a countably infinite vector space over the field with two elements.

5. Thanks! That clears up all of my problems. Now, I'm studying another proof of Erdos. This time, the proof of Bertrand's postulate. I'm following wikipedia's outline of the argument. I've made it quite far without getting confused. However, I don't understand the part that says " When p > sqrt(2n), the number (2n, n) has at most one factor of p. I would like to see a proof of that. Second, I don't see how that plays into the following argument using Lemma 2.

6. I just figured out the answers to my own questions. Nevermind.