Results 1 to 6 of 6

Math Help - proof involving least common multiple

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    proof involving least common multiple

    For every choice of non zero integers a,b,c, the integer lcm[a,c] divides
    the integer lcm[a,b] * lcm[b,c] / b.

    I was thinking of letting a=p/q, b=r/s, c=t/u. Then, somehow, the integer lcm[a,b] * lcm[b,c] / b will factor out an lcm[a,c], but I am not sure how to prove it that way.
    Last edited by comssa; October 25th 2009 at 06:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2009
    Posts
    22
    I thought about it, and this is what I got so far:

    lcm[a,b] = ab/(a,b), and so on.

    (a,c)=ax+cy
    (a,b)=ax+by
    (b,c)=bx+cy

    (a,b)(b,c)=(ax+by)(bx+cy)=(abx^2 + acxy+ b^2 xy + bcy^2)
    I am not sure how to factor a ax+cy out of that...
    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
    Let p_1,...,p_n be the set of primes which divide either one of a,b \mbox{ or } c. Write

    a=p_1^{\alpha_1}\hdots p_n^{\alpha_n}

    b=p_1^{\beta_1}\hdots p_n^{\beta_n}

    c=p_1^{\gamma_1}\hdots p_n^{\gamma_n}

    be the canonical factorizations of a,b,c, where some of the exponents may be 0. Then, letting M(x,y)=\mbox{max }\{x,y\},

    \mbox{lcm }(a,b)=p_1^{M(\alpha_1,\beta_1)}\hdots p_n^{M(\alpha_n,\beta_n)}

    \mbox{lcm }(b,c)=p_1^{M(\gamma_1,\beta_1)}\hdots p_n^{M(\gamma_n,\beta_n)}

    and hence

    \frac{\mbox{lcm }(a,b)\mbox{lcm }(b,c)}{b}=p_1^{M(\alpha_1,\beta_1)+M(\gamma_1,\be  ta_1)-\beta_1}\hdots p_n^{M(\alpha_n,\beta_n)+M(\gamma_n,\beta_n)-\beta_n}

    Now you just need to show that, for every 1 \leq j \leq n, we have M(\alpha_j,\beta_j)+M(\gamma_j,\beta_j)-\beta_j\geq M(\alpha_j,\gamma_j). Hint : consider separately the case where M(\alpha_j,\gamma_j)=\alpha_j and the case where M(\alpha_j,\gamma_j)=\gamma_j.
    Last edited by Bruno J.; October 26th 2009 at 07:55 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18
    Thanks.

    Shouldn't the two cases be M(\alpha_j,\gamma_j)=\alpha_j and M(\alpha_j,\gamma_j)=\gamma_j?



    If so, would this be ok?
    If M(\alpha_j,\gamma_j)=\alpha_j, then \alpha_j \geq \gamma_j
    If \beta_j \geq \alpha_j, then we have \beta_j + \beta_j - \beta_j \geq \alpha_j, which is true.
    If \beta_j \leq \alpha_j, then we have \alpha_j + M(\gamma_j,\beta_j) - \beta_j \geq \alpha_j, which is true because then M(\gamma_j,\beta_j) \geq \beta_j

    If M(\alpha_j,\gamma_j)=\gamma_j, then \alpha_j \leq \gamma_j
    If \beta_j \geq \gamma_j, then we have \beta_j + \beta_j - \beta_j \geq \gamma_j, which is true.
    If \beta_j \leq \gamma_j, then we have \gamma_j + M(\alpha_j,\beta_j) - \beta_j \geq \gamma_j, which is true because then M(\alpha_j,\beta_j) \geq \beta_j
    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
    Flawless! Good job.

    There may be a shorter way... but when you have proofs with greatest common divisors and least common multiples, a guaranteed path to success is to translate the identity you wish to prove as a statement about the canonical factorization of the numbers involved. It might be hard work but it always takes you where you want to go - just be careful choosing a good notation so you don't hit a brick wall.

    I corrected my post above - thanks for the heads up
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    I know this is done, but I just wanted to point something out that could help in the future ...

    This was written down:
    (a,c)=ax+cy
    (a,b)=ax+by
    (b,c)=bx+cy

    But we can not assume that all the x and y are the same ... that's the bit that could help in the future ... make sure you distinguish your variables:


    Another way to prove this is:

    definition of lcm[a,b]=d is the d is the smallest integer such that a|d and b|d
    let [a,b] = d, [a,c] = e, and [b,c] = f
    since b|d and b|f, let bx=d and by=f

    We are trying to show that [a,c]|[a,b][b,c]/b ... in other words, e|df/b

    df/b = bxf/b = xf and since c|f, c|df/b
    df/b = dby/b = dy and since a|d, a|df/b

    So a|df/b and c|df/b ... so df/b is a common multiple of a and c ... can you show that the [a,c] divides this common multiple?
    Last edited by Bingk; October 28th 2009 at 04:07 PM. Reason: clarification
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 25th 2011, 04:38 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Least common multiple of multiple numbers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 7th 2009, 09:18 PM
  4. Replies: 2
    Last Post: March 14th 2009, 03:56 AM
  5. least common multiple
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 14th 2006, 12:58 PM

Search Tags


/mathhelpforum @mathhelpforum