Results 1 to 9 of 9

Thread: Product of Primes

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    19

    Product of Primes

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

    Show that both of these identities cannot be true simultanously:

    $\displaystyle
    \prod_{i=1}^{k}q_i = p^\alpha+2
    $

    $\displaystyle
    \prod_{i=1}^{k}(q_i-1) = p^\alpha+2-p^{\alpha-1}
    $

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

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,775
    Thanks
    3028
    Quote Originally Posted by wauwau View Post
    Let $\displaystyle q_i, p$ be distinct odd primes $\displaystyle \alpha,k>1$ positive integer

    Show that both of these identities cannot be true simultanously:

    $\displaystyle
    \prod_{i=1}^{k}q_i = p^\alpha+2
    $

    $\displaystyle
    \prod_{i=1}^{k}(q_i-1) = p_i^\alpha+2-p^{\alpha-1}
    $

    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 "$\displaystyle 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 $\displaystyle q_i$ , and combined with the second equality, we have:
    $\displaystyle 2^k-1=p^{\alpha-1}$ (&)
    thus $\displaystyle \alpha$ is not greater than k.
    combined with the first equality, gives p is less than the greatest prime among $\displaystyle q_i$.
    from (&), we see that
    $\displaystyle \prod_{i=1}^{k}q_i = p^\alpha+2 = p(2^k-1)+2 < 2^kp$
    that is impossible since $\displaystyle 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 $\displaystyle q_i$ , and combined with the second equality, we have:
    $\displaystyle 2^k-1=p^{\alpha-1}$ (&)
    thus $\displaystyle \alpha$ is not greater than k.
    combined with the first equality, gives p is less than the greatest prime among $\displaystyle q_i$.
    from (&), we see that
    $\displaystyle \prod_{i=1}^{k}q_i = p^\alpha+2 = p(2^k-1)+2 < 2^kp$
    that is impossible since $\displaystyle q_i,p$ are distinct odd prime!

    is it correct?
    Can you explain, where the $\displaystyle 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.
    $\displaystyle 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.
    $\displaystyle 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 $\displaystyle 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: Sep 14th 2011, 04:54 PM
  2. Prove that (product of primes between n and 2n) > 2^n
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 17th 2010, 02:45 PM
  3. product of primes
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 13th 2010, 10:24 AM
  4. product of primes II
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 3rd 2010, 01:37 PM
  5. Product of primes using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 21st 2009, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum