Results 1 to 11 of 11

Thread: 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
    5
    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; Dec 7th 2006 at 03:51 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,829
    Thanks
    2852
    Awards
    1
    Is it clear to you that gcd(a,b)|c?
    Now lcm(a,b)*gcd(a,b)=ab|$\displaystyle 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,
    $\displaystyle a,b>0$.

    Let, $\displaystyle d=\gcd(a,b)$
    And we can define a positive integer,
    $\displaystyle m=\frac{ab}{d}$.
    Let, $\displaystyle c$ be a common multiple of $\displaystyle a,b$.
    We need to show,
    $\displaystyle m\leq c$
    Note,*)
    $\displaystyle \frac{c}{m}=\frac{cd}{md}=\frac{c(ax+by)}{ab}=\fra c{c}{b}\cdot x+\frac{c}{a}\cdot y$
    Where,
    $\displaystyle \frac{c}{b},\frac{c}{a} \in \mathbb{Z}^+$ because it is a common multiple.
    Thus, $\displaystyle m|c$.
    That means,
    $\displaystyle m\leq c$.
    Thus,
    $\displaystyle \mbox{lcm}(a,b)=m$
    Thus,
    $\displaystyle \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,
    $\displaystyle \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
    363
    Thanks
    2
    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.
    $\displaystyle a|c$
    $\displaystyle c = x\cdot a$, where $\displaystyle x\ \epsilon\ N$

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

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

    $\displaystyle 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
    363
    Thanks
    2
    $\displaystyle a|c\ \Rightarrow\ c\ =\ x\cdot a$

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

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

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

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

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum