Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving with GCD and LCM

  1. Oct 27, 2004 #1
    Let a, b, and c be positive integers.

    I need to prove two items...

    1. abc = GCD(a,b,c) * LCM(ab,bc,ac)
    2. abc = GCD(ab,ac,bc) * LCM(a,b,c)

    where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple.

    Could I go ahead and say that (a,b,c)=1, that is relatively prime? Am I wrong in saying this part? If so, what could I say to make it right?
     
  2. jcsd
  3. Oct 28, 2004 #2
    They have to be pairwise prime. We might have a case like (5,5,1) =1.
     
  4. Oct 28, 2004 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Look here:

    http://mathworld.wolfram.com/LeastCommonMultiple.html

    If we prime factorize a, b, and c as follows:

    [tex]a = p_1^{a_1} \dots p_n^{a_n}[/tex]

    [tex]b = p_1^{b_1} \dots p_n^{b_n}[/tex]

    [tex]c = p_1^{c_1} \dots p_n^{c_n}[/tex]

    Where [itex]p_n[/itex] is the greatest prime occuring in at least one of the prime factorizations of a, b, and c, and where [itex]a_i = 0[/itex] if [itex]p_i[/itex] doesn't occur in the prime factorization of a (and similar things go for b and c), then:

    [tex]LCM(ab, bc, ca) = \prod _{i = 1} ^n p_i^{\max \{a_i + b_i, b_i + c_i, c_i + a_i \}}[/tex]

    See the page on the same site about the GCD, and we can say:

    [tex]GCD(a, b, c) = \prod _{i = 1} ^n p_i^{\min \{a_i, b_i, c_i \}}[/tex]

    Multiplying the two, we get:

    [tex]\prod _{i = 1} ^n p_i^{\min \{a_i, b_i, c_i \} + \min \{a_i + b_i, b_i + c_i, c_i + a_i\}} = \prod _{i = 1} ^n p_i^{a_i + b_i + c_i} = abc[/tex]

    as required. Something similar can be done for the other proposition. I think, however, that you might want to prove that LCM and GCD can be expressed as such products (which I doubt will be too difficult).
     
    Last edited: Oct 28, 2004
  5. Nov 13, 2004 #4

    lurflurf

    User Avatar
    Homework Helper

    Edited: to note that i just saw AGK did the exact same thing.

    I need to prove two items...

    1. abc = GCD(a,b,c) * LCM(ab,bc,ac)
    2. abc = GCD(ab,ac,bc) * LCM(a,b,c)

    where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple.

    let fp:N->Union(N,{0}) (N the set of natural numbers {1,2,...})
    s.t. fp(n)=k=>k is the largest whole number for which p^k|n
    we can assume p is prime though we need not

    lemma:
    fp(n)=fp(m) for all p in P (P the set of prime numbers)=> n=m
    (proof obvious by unique prime factorization)

    fp has some useful properties
    fp(n*m)=fp(n)+fp(m)
    fp(GCD(a(1),...,a(n))=min({fp(a(1),...,fp(a(n))})
    fp(LCD(a(1),...,a(n))=max({fp(a(1),...,fp(a(n))})

    so using this on (1)
    fp(abc)=fp(a)+fp(b)+fp(c)
    fp(GCD(a,b,c) * LCM(ab,bc,ac))=fp(GCD(a,b,c))+fp(LCM(ab,bc,ac))
    =min({fp(a),fp(b),fp(c)})+max({fp(ab),fp(bc),fp(ac)}
    =min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b),fp(b)+fp(c),fp(a)+fp(c)}
    =min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b)+fp(c)-fp(c),fp(a)+fp(b)+fp(c)-fp(a),fp(a)+fp(b)+fp(c)-fp(b)}
    =min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b)+fp(c)-fp(a),fp(a)+fp(b)+fp(c)-fp(b),fp(a)+fp(b)+fp(c)-fp(c)}
    =min({fp(a),fp(b),fp(c)})+fp(a)+fp(b)+fp(c)-min({fp(a),fp(b),fp(c)}
    fp(GCD(a,b,c) * LCM(ab,bc,ac))=fp(a)+fp(b)+fp(c)
    thus
    fp(abc)=fp(GCD(a,b,c) * LCM(ab,bc,ac))
    p was arbitrary so
    abc=GCD(a,b,c) * LCM(ab,bc,ac)

    (2) can be do by the same method.
     
    Last edited: Nov 13, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proving with GCD and LCM
  1. Gcd and lcm (Replies: 59)

Loading...