Results 1 to 2 of 2

Math Help - Gcd/lcm

  1. #1
    Junior Member
    Joined
    Sep 2012
    From
    New York
    Posts
    55

    Gcd/lcm

    For non-zero integers a & b verify the following condition are equivalent.

    a) a divides b

    b) gcd(a,b)= (Absolute value of a)

    c) lcm(a,b)= (Absolute value of b)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Gcd/lcm

    When you're asked to "show the following are equivalent", the idea is create a "path of implication" so that, thinking of it as a directed graph, once you are at one vertices (meaning one of those conditions is true), the implications take you through all the verticies (meaning all the statements are true). Such a "path" isn't unique.
    For instance, you could prove it this way: Prove A if-and-only-if B (A implies B and B implies A) and prove A if-and-only-if C.
    But the most efficient way is to prove it as a "ring": Prove A implies B, and prove B implies C, and prove C implies A.
    With three statements it's easy, but it can be unclear how to proceed (there are lot's of choices of how to try) when there are many statement.

    I'll do one step: B implies C:
    Claim: gcd(a,b)= |a| implies lcm(a,b) = |b|.
    Proof:
    Let gcd(a,b) = |a|. First note that the property of being an integer multiple or divisor of another integer is unchanged by sign.
    Since gcd(a,b)= |a|, have that a divides |b|. Also always have that b divides |b|. Since both a and b divide |b|, the lcm(a,b) divides |b|.
    But lcm(a,b) is a multiple of |b|, so |b| divides lcm(a,b).
    Since have that lcm(a,b) divides |b|, and |b| divides lcm(a,b), by the Lemma below, it follows that lcm(a,b) = |lcm(a,b)| = |b|. QED (B implies C).

    Lemma: If u, v nonzero integers such that u divides v and v divides u, then |u| = |v|.
    Proof:
    The givens say that v = ru, and u = sv for some integers r, s. But then u = sv = s(ru) = (sr)u, so (sr-1)u = 0.
    But (rs-1)u = 0 and u not zero, so have that rs-1 = 0. Therefore rs = 1.
    But because r and s are integers, rs=1 forces that either r=s=1 or r=s=-1.
    Either way |r|=|s|=1.
    Thus v = ru implies |v| = |r||u| = |u|, which proves the lemma.
    Last edited by johnsomeone; September 19th 2012 at 05:10 PM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum