Results 1 to 2 of 2

Thread: Gcd/lcm

  1. #1
    Junior Member
    Sep 2012
    New York


    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
    MHF Contributor
    Sep 2012
    Washington DC USA

    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|.
    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|.
    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; Sep 19th 2012 at 05:10 PM.
    Follow Math Help Forum on Facebook and Google+

Search tags for this page

Search Tags

/mathhelpforum @mathhelpforum