Erdos proof Sum of Reciprocals of Primes

**grandunification** · November 20th 2010, 03:32 PM

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.

**Bruno J.** · November 20th 2010, 04:33 PM

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.

**grandunification** · November 21st 2010, 10:15 AM

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.

**Bruno J.** · November 21st 2010, 02:29 PM

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.

**grandunification** · November 27th 2010, 11:07 AM

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.

**grandunification** · November 27th 2010, 01:36 PM

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

Thread: Erdos proof Sum of Reciprocals of Primes

LinkBack

Thread Tools

Display

Erdos proof Sum of Reciprocals of Primes

Similar Math Help Forum Discussions

Odd Primes Proof (Should be simple)

Proof of primes

Mod proof with primes

Proof of primes.

Primes proof

Search Tags