Results 1 to 6 of 6

Thread: 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; Oct 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 $\displaystyle p_1,...,p_n$ be the set of primes which divide either one of $\displaystyle a,b \mbox{ or } c$. Write

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

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

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

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

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

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

    and hence

    $\displaystyle \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 $\displaystyle 1 \leq j \leq n$, we have $\displaystyle M(\alpha_j,\beta_j)+M(\gamma_j,\beta_j)-\beta_j\geq M(\alpha_j,\gamma_j)$. Hint : consider separately the case where $\displaystyle M(\alpha_j,\gamma_j)=\alpha_j$ and the case where $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$.
    Last edited by Bruno J.; Oct 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 $\displaystyle M(\alpha_j,\gamma_j)=\alpha_j$ and $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$?



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

    If $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$, then $\displaystyle \alpha_j \leq \gamma_j$
    If $\displaystyle \beta_j \geq \gamma_j$, then we have $\displaystyle \beta_j + \beta_j - \beta_j \geq \gamma_j$, which is true.
    If $\displaystyle \beta_j \leq \gamma_j$, then we have $\displaystyle \gamma_j + M(\alpha_j,\beta_j) - \beta_j \geq \gamma_j$, which is true because then $\displaystyle 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; Oct 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: Jan 25th 2011, 04:38 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Oct 25th 2010, 05:45 AM
  3. Least common multiple of multiple numbers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Dec 7th 2009, 09:18 PM
  4. Replies: 2
    Last Post: Mar 14th 2009, 03:56 AM
  5. least common multiple
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 14th 2006, 12:58 PM

Search Tags


/mathhelpforum @mathhelpforum