Results 1 to 8 of 8

Math Help - LCM problem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    LCM problem

    Q: Prove if a|k, b|k, then lcm(a,b)|k.

    (Hint: LCM of non-zero intergers a and b is the smallest postive integer m such that a|m, b|m)

    Please help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tttcomrader View Post
    Q: Prove if a|k, b|k, then lcm(a,b)|k.

    (Hint: LCM of non-zero intergers a and b is the smallest postive integer m such that a|m, b|m)

    Please help!
    Say these are positive integers.
    ---
    a|c \mbox{ and }b|c.

    Use this to show that,
     ab | cd where d=\gcd(a,b).

    Then that means,
    \left( \frac{ab}{d} \right) | c

    But,
    \frac{ab}{d} =\mbox{lcm}(a,b).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Neils Henrik Abel
    Use this to show that,
     ab | cd where d=\gcd(a,b).
    Here are the all the details if you need them.
    ---
    a|c \Rightarrow c = ak \  \exists  \  k\in \mathbb{Z}
    b|c \Rightarrow c = bj \ \exists \ j \in \mathbb{Z}

    Let d=\gcd(a,b) then that means:
    d = ax+by \ \exists \ x,y\in \mathbb{Z}

    Now, by the above statements,
    cd = c(ax+by) = acx + bcy = abjx+abky = ab(jx+ky) \Rightarrow ab|cd

    Definition: Let a|b. For a\not =0 we define \frac{b}{a} = c so that b=ac.

    Theorem: Let a|bc and c|a \mbox{ with }c\not =0. Then \left( \frac{a}{c} \right) | b.

    Proof: Again, just follow the definitions.
    a|bc \Rightarrow bc = ka \ \exists \ k\in \mathbb{Z}
    c|a \Rightarrow a=cj \ \exists \ j \in \mathbb{Z} \mbox{ and } j = \frac{a}{c}
    Substitute second equation into first,
    bc = kcj
    Since c\not =0 we have,
    b=kj \Rightarrow j | b \Rightarrow \left( \frac{a}{c}\right) | b
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    The k that you use in your proof with c = ak, is that the same k as the one given in the problem?

    And how does the lcm = m fit in this?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tttcomrader View Post
    The k that you use in your proof with c = ak, is that the same k as the one given in the problem?
    No. I used different letters.
    And how does the lcm = m fit in this?
    Because I show that,
    \left(\frac{ab}{d} \right) | c
    But,
    \frac{ab}{d} = \frac{ab}{\gcd(a,b)} = \mbox{lcm}(a,b).

    Thus, \mbox{lcm}(a,b)|c.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    I understand this proof, but would you mind proving the theorem? I don't understand how a|bc and c|a would implies (a/c)|b.

    thanks so much!
    Last edited by tttcomrader; June 5th 2007 at 12:21 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tttcomrader View Post
    I don't understand how a|bc and c|a would implies (a/c)|b.
    What are you talking about? I proved the theorem above. Do you understand it?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    Oh, I missed that last part, now I fully understand it, thanks!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum