Results 1 to 6 of 6

Math Help - Erdos proof Sum of Reciprocals of Primes

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    31

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by grandunification View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    31
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by grandunification View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2009
    Posts
    31
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2009
    Posts
    31
    I just figured out the answers to my own questions. Nevermind.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Odd Primes Proof (Should be simple)
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: May 14th 2010, 11:42 AM
  2. Proof of primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 10th 2010, 08:35 PM
  3. Mod proof with primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 06:32 PM
  4. Proof of primes.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 26th 2009, 12:12 AM
  5. Primes proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2005, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum