Results 1 to 11 of 11

Math Help - If a|c and b|c prove [a,b]|c ([a,b] represents lcm of a and b).

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    12

    If a|c and b|c prove [a,b]|c ([a,b] represents lcm of a and b).

    So, I know that c=aq and c=br for some integers q and r. I also know and can prove that c is greater than or equal to d, thus c=dz + t for some integers z and t by Euclid's algorithm. We know that t is greater than or equal to zero and less than d. If we can show d|t, then we know t=0. From here, we have c=dz, thus d|c and by substitution, [a,b]|c and we're done.

    The part I don't get is this. How do you show d|t? If I knew how to do this, I could do the rest of the problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Geoffrey View Post
    So, I know that c=aq and c=br for some integers q and r. I also know and can prove that c is greater than or equal to d, thus c=dz + t for some integers z and t by Euclid's algorithm. We know that t is greater than or equal to zero and less than d. If we can show d|t, then we know t=0. From here, we have c=dz, thus d|c and by substitution, [a,b]|c and we're done.

    The part I don't get is this. How do you show d|t? If I knew how to do this, I could do the rest of the problem.
    If I were doing this I would consider the prime decomposition of a, b, c and [ab].

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    12
    Yes, but I'm not allowed to assume that, so I have to be creative. I could use it if I proved every number has a prime decomposition though, and then use that to prove my theorem, but I don't know how to do that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2006
    Posts
    12
    Okay, I'm stuck. If you all have time, please show me how to prove: if a|c and b|c then [a,b]|c.
    Last edited by Geoffrey; December 7th 2006 at 04:51 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,912
    Thanks
    1760
    Awards
    1
    Is it clear to you that gcd(a,b)|c?
    Now lcm(a,b)*gcd(a,b)=ab| c^2.
    From the above is it possible to conclude that gcd(a,b)|c?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2006
    Posts
    12
    Plato, I am not allowed to assume what you just suggested. Indeed, the next problem is this: Prove lcm(a,b) x gcd(a,b) = ab
    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 Geoffrey View Post
    Plato, I am not allowed to assume what you just suggested. Indeed, the next problem is this: Prove lcm(a,b) x gcd(a,b) = ab
    Say,
    a,b>0.

    Let, d=\gcd(a,b)
    And we can define a positive integer,
    m=\frac{ab}{d}.
    Let, c be a common multiple of a,b.
    We need to show,
    m\leq c
    Note,*)
    \frac{c}{m}=\frac{cd}{md}=\frac{c(ax+by)}{ab}=\fra  c{c}{b}\cdot x+\frac{c}{a}\cdot y
    Where,
    \frac{c}{b},\frac{c}{a} \in \mathbb{Z}^+ because it is a common multiple.
    Thus, m|c.
    That means,
    m\leq c.
    Thus,
    \mbox{lcm}(a,b)=m
    Thus,
    \gcd(a,b)\mbox{lcm}(a,b)=ab.
    Not only it proves this, it answers your other question.



    *)Using the fudamental property of greatest common divisors,
    \gcd(a,b)=ax+by
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2006
    Posts
    12
    Not only it proves this, it answers your other question.
    Okay, I follow your proof so far, and it all makes sense, but exactly how does it prove that if a|c and b|c, then lcm(a,b)|c? I'm sure the answer is pretty obvious, but I'm just having trouble seeing it.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by Geoffrey View Post
    Okay, I follow your proof so far, and it all makes sense, but exactly how does it prove that if a|c and b|c, then lcm(a,b)|c? I'm sure the answer is pretty obvious, but I'm just having trouble seeing it.
    a|c
    c = x\cdot a, where x\ \epsilon\ N

    b|c
    b|x\cdot a
    Divide both sides by gcd(a,\ b)
    \frac{b}{gcd(a,\ b)}|x\cdot \frac{a}{gcd(a,\ b)}
    But gcd\left(\frac{b}{gcd(a,\ b)},\ \frac{a}{gcd(a,\ b)}\right)\ =\ 1
    \frac{b}{gcd(a,\ b)}|x

    \frac{a\cdot b}{gcd(a,\ b)}|x\cdot a

    lcm(a,\ b)|c

    This looks similar to the Chinese remainder theorem.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2006
    Posts
    12
    I just found out that I am not allowed to work with numbers like (a/b). I must only work in integers, and cannot express them as fractions. My teacher will only let me use the multiplication, addition, and subtraction operators. Your proofs are helpful, but I have no clue how to express them without using division. (Oh, divides | is okay. | is acceptable)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    a|c\ \Rightarrow\ c\ =\ x\cdot a

    b|c\ \Rightarrow\ b|x\cdot a

    b|x\cdot gcd(a,\ b)

    a\cdot b|x\cdot a\cdot gcd(a,\ b)

    a\cdot b|c\cdot gcd(a,\ b)

    lcm(a,\ b)|c
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 2nd 2011, 08:17 AM
  2. limit that represents derivative of a function
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: August 8th 2008, 09:41 PM
  3. not sure about what this limit represents
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 14th 2008, 02:28 PM
  4. Vector Function that represents the Curve
    Posted in the Calculus Forum
    Replies: 6
    Last Post: March 8th 2008, 11:33 PM
  5. represents points as curve
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 25th 2007, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum