Results 1 to 9 of 9

Math Help - Product of Primes

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    19

    Product of Primes

    Let q_i, p be distinct odd primes \alpha,k>1 positive integer

    Show that both of these identities cannot be true simultanously:

     <br />
\prod_{i=1}^{k}q_i = p^\alpha+2<br />

     <br />
\prod_{i=1}^{k}(q_i-1) = p^\alpha+2-p^{\alpha-1}<br />

    I have proved it for k=2 but have no idea how to prove it for higher k
    Last edited by wauwau; December 20th 2009 at 01:11 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,418
    Thanks
    1854
    Quote Originally Posted by wauwau View Post
    Let q_i, p be distinct odd primes \alpha,k>1 positive integer

    Show that both of these identities cannot be true simultanously:

     <br />
\prod_{i=1}^{k}q_i = p^\alpha+2<br />

     <br />
\prod_{i=1}^{k}(q_i-1) = p_i^\alpha+2-p^{\alpha-1}<br />

    I have proved it for k=2 but have no idea how to prove it for higher k
    Try "proof by induction". But you have " p_i in your second formula and you have not defined it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    19
    I have corrected the error.

    But since the right sides of the equation change completely when you increase the k there is no way of attacking this with induction - from my point of view!!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    the euler function give me some idea, but I didn't solve it completely yet.
    You can try, I wish you success!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    If we apply the euler function to the product of q_i , and combined with the second equality, we have:
    2^k-1=p^{\alpha-1} (&)
    thus \alpha is not greater than k.
    combined with the first equality, gives p is less than the greatest prime among q_i.
    from (&), we see that
    \prod_{i=1}^{k}q_i = p^\alpha+2 = p(2^k-1)+2 < 2^kp
    that is impossible since  q_i,p are distinct odd prime!

    is it correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2009
    Posts
    19
    Quote Originally Posted by Shanks View Post
    If we apply the euler function to the product of q_i , and combined with the second equality, we have:
    2^k-1=p^{\alpha-1} (&)
    thus \alpha is not greater than k.
    combined with the first equality, gives p is less than the greatest prime among q_i.
    from (&), we see that
    \prod_{i=1}^{k}q_i = p^\alpha+2 = p(2^k-1)+2 < 2^kp
    that is impossible since  q_i,p are distinct odd prime!

    is it correct?
    Can you explain, where the 2^k-1 comes from?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    apply the euler phi function to the product of q_i.
    2^k-1 is the number of numbers which satisfy
    (1)not greater than the product of q_i.
    (2)not relatively prime to the product of q_i.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Shanks View Post
    apply the euler phi function to the product of q_i.
    2^k-1 is the number of numbers which satisfy
    (1)not greater than the product of q_i.
    (2)not relatively prime to the product of q_i.
    How so? You're saying that q_1\dots q_k - \varphi(q_1\dots q_k) = 2^k-1? If so, this is clearly false.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Thanks,I know where I go wrong!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Product of perfect square and primes
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 14th 2011, 05:54 PM
  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, 03:45 PM
  3. product of primes
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 13th 2010, 11:24 AM
  4. product of primes II
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 3rd 2010, 02:37 PM
  5. Product of primes using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 21st 2009, 09:45 AM

Search Tags


/mathhelpforum @mathhelpforum