Results 1 to 2 of 2

Math Help - least common multiple and division theorem

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    21

    least common multiple and division theorem

    Q: (We denote the least common multiple of a and b by [a,b] or lcm[a,b])

    Give a proof by contradiction that if a positive integer n is a common multiple of a and b then [a,b] divides n.

    (Hint: Use the division theorem. If [a,b] does not divide n then n=[a,b]q+r where 0<r<[a,b]. Now prove that r is a common multiple of a and b.)







    My proof that r is a common multiple of a and b:
    r=n-[a,b]q
    n=au=av
    [a,b]=m=ax=by

    r=a(u-xq)=b(v-yq)

    Is that correct? Also, how does r being a common multiple of a and b provide a contradiction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    What you did is correct save for a typo.

    <br />
r = n - {\text{lcm}}\left( {a,b} \right) \cdot q<br />

    Okay you know that <br />
r<br />
is a common multiple of a and b. We have 0\le r<\text{lcm}(a,b) (1) by the definition of the remainder.

    Now remember the definition of Least Common Multiple. \text{lcm}(a,b)=<br />
\min \left\{ {x \in \mathbb{Z}^ +  /x = \dot a \wedge x = \dot b} \right\}<br />
(2) In other words, it is the smallest positive integer such that it is a multiple of both a and b.

    So in our case, if r >0 then r is positive integer which is a common multiple of a and b, and in fact smaller (1) than the smallest positive integer satisfying this (2)! This is a contradiction!

    Thus it must be -only case remaining- r=0 which is indeed a common multiple of a and b
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 25th 2011, 04:38 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Least common multiple of multiple numbers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 7th 2009, 09:18 PM
  4. Replies: 2
    Last Post: March 14th 2009, 03:56 AM
  5. least common multiple
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 4th 2008, 03:29 AM

Search Tags


/mathhelpforum @mathhelpforum