Results 1 to 8 of 8

Thread: 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
    10
    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.
    ---
    $\displaystyle a|c \mbox{ and }b|c$.

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

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

    But,
    $\displaystyle \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
    10
    Quote Originally Posted by Neils Henrik Abel
    Use this to show that,
    $\displaystyle ab | cd$ where $\displaystyle d=\gcd(a,b)$.
    Here are the all the details if you need them.
    ---
    $\displaystyle a|c \Rightarrow c = ak \ \exists \ k\in \mathbb{Z}$
    $\displaystyle b|c \Rightarrow c = bj \ \exists \ j \in \mathbb{Z}$

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

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

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

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

    Proof: Again, just follow the definitions.
    $\displaystyle a|bc \Rightarrow bc = ka \ \exists \ k\in \mathbb{Z}$
    $\displaystyle c|a \Rightarrow a=cj \ \exists \ j \in \mathbb{Z} \mbox{ and } j = \frac{a}{c}$
    Substitute second equation into first,
    $\displaystyle bc = kcj $
    Since $\displaystyle c\not =0$ we have,
    $\displaystyle 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
    10
    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,
    $\displaystyle \left(\frac{ab}{d} \right) | c$
    But,
    $\displaystyle \frac{ab}{d} = \frac{ab}{\gcd(a,b)} = \mbox{lcm}(a,b)$.

    Thus, $\displaystyle \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; Jun 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
    10
    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