Results 1 to 3 of 3

Math Help - Help with a problem involving the GCD, LCM.

  1. #1
    Newbie
    Joined
    Apr 2010
    From
    Ohio
    Posts
    12

    Help with a problem involving the GCD, LCM.

    Let a and b be positive integers, and let m be an integer such that ab=m(a,b). Without using the prime factorization theorem, prove that (a,b)[a,b]=ab by verifying that m satisfies the necessary properties of [a,b].

    Note that (a,b) denotes the GCD of a and b and [a,b] denotes the LCM of a and b.

    Here is the definition for LCM that I have (the two properties that I need to show.)

    A positive integer m is called the least common multiple of the nonzero integers a and b if

    (i) m is a multiple of both a and b, and

    (ii) any multiple of both a and b is also a multiple of m.

    Property (i) was not very difficult to show, but I am struggling with the second one. Here is what I have so far.

    Let a|q and b|q, where q\in\mathbb{Z}.

    Then q=ax and q=by, where x,y\in\mathbb{Z}

    ==>\quad qb=abx\quad and qa=aby

    ==>\quad qb=mdx\quad and qa=mdy

    ==>\quad qhd=mdx\quad and qkd=mdy

    ==>\quad qh=mx\quad and qk=my

    ==>\quad m|qh\quad and m|qk.

    That is as much as I can get. How can I show that m|q?

    Any hints would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Edit: See here

    Basic Number Theory: LCM/GCD Proof

    (Make sure to read posts #1 through #4 to get a full treatment of part (2).)

    Although the proof for part (1) is lengthy for my taste, since

    \displaystyle ab=m(a,b)\implies m=a\left(\frac{b}{(a,b)}\right)

    And since (a,b) | b, we know \frac{b}{(a,b)} is an integer, hence a | m, and by symmetry b | m also.

    Edit 2: I think aman_cc's proof for part (2) below is nicer than the one on the other forum.
    Last edited by undefined; October 4th 2010 at 08:26 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Hint use the fact that

    xa + yb = (a,b) for some integers x,y
    xaq + ybq = (a,b)q
    divide the whole eq by ab
    xq/b + yq/a = q/m
    it should be easy from here
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Problem involving Similarities!
    Posted in the Geometry Forum
    Replies: 3
    Last Post: November 26th 2010, 04:50 AM
  2. Problem involving Hooke's Law
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: February 15th 2010, 05:27 AM
  3. Problem involving f'
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 29th 2009, 04:49 PM
  4. Problem involving work
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 17th 2009, 06:17 PM
  5. Problem involving work
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 30th 2008, 05:16 PM

/mathhelpforum @mathhelpforum