Results 1 to 5 of 5

Math Help - product of primes

  1. #1
    Newbie vincent's Avatar
    Joined
    Mar 2010
    From
    Montreal
    Posts
    12

    product of primes

    If p are primes and m any integer, show that \prod_{p\leq m+1} p \leq 4^m, i was told it can be done by induction but still can't prove it...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by vincent View Post
    If p are primes and m any integer, show that \prod_{p\leq m+1} p \leq 4^m, i was told it can be done by induction but still can't prove it...
    I'll let you verify the base case.

    So assume true for all  i\leq m and let's use this to show the case for  m+1 is true too.

    Now, we have that  2^{m+1}\geq{m+1 \choose \lfloor (m+1)/2 \rfloor} \geq \prod_{\lfloor (m+1)/2 \rfloor \leq p <m+1} p

    By our inductive hypothesis,  \prod_{p\leq\lfloor (m+1)/2\rfloor} p \leq 4^{\lfloor (m+1)/2\rfloor-1} = 2^{2\lfloor (m+1)/2\rfloor-2}

    So  2^{m+1}\cdot2^{2\lfloor (m+1)/2\rfloor-2}\geq\prod_{p\leq m+1} p

    Notice that  m+1+2\lfloor (m+1)/2\rfloor-2 \leq m+1+2 (m+1)/2-2 = 2m

    Thus  2^{m+1}\cdot2^{2\lfloor (m+1)/2\rfloor-2}\leq 2^{2m} = 4^m .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    This beautiful theorem and proof are due to Erdös.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie vincent's Avatar
    Joined
    Mar 2010
    From
    Montreal
    Posts
    12
    wow thanks, it wasn't simple after all!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by vincent View Post
    wow thanks, it wasn't simple after all!
    Somebody gave you this problem as a challenge? That's mean!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Group Order a product of primes
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: November 19th 2010, 08:37 AM
  2. Prove that (product of primes between n and 2n) > 2^n
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 17th 2010, 02:45 PM
  3. product of primes II
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 3rd 2010, 01:37 PM
  4. Product of Primes
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 23rd 2009, 06:57 PM
  5. Product of primes using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 21st 2009, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum