Results 1 to 12 of 12

Math Help - Proof: Formula connecting GCD and LCM for 3 integers

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Post Proof: Formula connecting GCD and LCM for 3 integers

    Hi, I need some help proving that the below formula is true.

    It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

    [a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

    Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

    How can I use this to prove the formula? Please help.

    Katy.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by harkapobi View Post
    Hi, I need some help proving that the below formula is true.

    It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

    [a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

    Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

    How can I use this to prove the formula? Please help.

    Katy.
    If you are given prime factorization of a,b - would you know how to write GCD, LCM from the prime factorization?
    This equations seems like a direct application of that concept.

    Best is to take specific numbers and try it out to get a feel. Then you can generalize.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Yes, to write the GCD and LCM using prime factorisations;

    if a = ( p_1^ n_1)( p_2^ n_2).....( p_s^ n_s)
    and
    b = ( p_1^ m_1)( p_2^ m_2).....( p_s^ m_s)

    Then LCM[a,b] = ( p_1^ t_1)( p_2^ t_2).....( p_s^ t_s)

    Where t_i = max{ n_i, m_i}

    Is that right? And similar for GCD but with min instead of max. I've tried writing all this down on paper and I still can't see how it helps me prove the formula.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by harkapobi View Post
    Yes, to write the GCD and LCM using prime factorisations;

    if a = ( p_1^ n_1)( p_2^ n_2).....( p_s^ n_s)
    and
    b = ( p_1^ m_1)( p_2^ m_2).....( p_s^ m_s)

    Then LCM[a,b] = ( p_1^ t_1)( p_2^ t_2).....( p_s^ t_s)

    Where t_i = max{ n_i, m_i}

    Is that right? And similar for GCD but with min instead of max. I've tried writing all this down on paper and I still can't see how it helps me prove the formula.
    I have not tried it myself. First check of the equation actually is true. Take any 3 numbers and do a quick check.

    If it does, to prove, argue as follows
    Consider any prime p
    power of p in a,b,c be n1,n2,n3
    consider three cases
    - all three n1,n2,n3 differed, assume n1>n2>n3 (without loss of generality)
    - 2 of n1,n2,n3 same. Then either n1=n2>n3 or n1=n2<n3
    - all 3 same

    for each of the cases above show the power of p in LHS and RHS is same
    as p is any prime hence equality holds

    most probably it should work
    thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    So a=p^n1, b=p^n2 and c=p^n3?

    I see how to prove these work in the formula. Is substituting these into the formula for all 3 cases enough to prove that it works? Does this cover the cases where a,b or c are composed of more than one prime?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by harkapobi View Post
    So a=p^n1, b=p^n2 and c=p^n3?

    I see how to prove these work in the formula. Is substituting these into the formula for all 3 cases enough to prove that it works? Does this cover the cases where a,b or c are composed of more than one prime?
    Note we have proved for 'any' prime not a specific prime. Combined with Fundamental Theorem of Arithmetic, it is sufficient.

    I checked - the above logic works and is a valid proof. Why do you doubt?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Ok, thanks for your help

    I just like to be sure that I've done enough to prove it. I just have difficulty getting my head around these proofs
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by harkapobi View Post
    Hi, I need some help proving that the below formula is true.

    It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

    [a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

    Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

    How can I use this to prove the formula? Please help.

    Katy.

    it is long

    let

    r = the product of the similar primes from a,b,c and this equal =(a,b,c)

    n = the product of the similar primes from a,b except r =(a,b)/r

    m = the product of the similar primes from b,c except r =(b,c)/r

    o = the product of the similar primes from a,c except r =(a,c)/r

    [a,b] = ab/(a,b)

    we can say that :

    x= the product of the primes of a without n(o)r = a/n(o)r

    y= the product of the primes of b without n(m)r = b/n(m)r

    u = the product of the primes of c without m(o)r = c/m(o)r

    [a,b,c] = the product of the all primes in a,b,c but without taking the similar primes twice

    [a,b,c] = rmnoxyu sub the x,y,u values


    [a,b,c] =r\cdot n\cdot m\cdot o \frac{a}{nor}\cdot \frac{b}{nmr}\cdot \frac{c}{mor}

    [a,b,c] = r\cdot \frac{a}{nr} \cdot \frac{b}{mr} \cdot \frac{c}{or}

    but from above nr=(a,b) mr=(b,c) or=(a,c) so

    [a,b,c] = \frac{r \cdot a \cdot b \cdot c}{(a,b)(b,c)(a,c)}

    [a,b,c] = \frac{(a,b,c)abc}{(a,b)(b,c)(a,c)}

    I wish it is clear

    I made a picture it present a,b,c like a set the intersection between a and b present the similar primes of a,b

    and I made a name for every part in the pic and [a,b,c] is the whole picture (i.e the product of all parts in the picture)

    it is like the union and intersection of sets but here present the product of the similar primes of the two sets
    Attached Thumbnails Attached Thumbnails Proof: Formula connecting GCD and LCM for 3 integers-col.jpg  
    Last edited by Amer; October 22nd 2009 at 11:06 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    wow, thats difficult to get my head around. The picture helps tho Thanks.

    But I dont understand why [a, b, c] = rmnoxyu ? I get lost somewhere at that point.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    ok

    [a,b,c] how you can find it for example let


    a=p^4\times q^5\times g^2\times h^2

    b=p^3\times q^8 \times g^3\times k

    c=p^2\times q^4 \times g^4 \times k^2 \times l

    [a,b,c] = p^4 \times q^8 \times g^4 \times k^2 \times h^2 \times l

    p,q,g,h,l is prime numbers

    to find [a,b,c] what I do is let

    r = similar primes from a,b,c = p^2 \times q^4 \times g^2

    n = similar primes from a,b but without the r =  p \times q

    m= similar primes from b,c without r = g (k)

    o = similar primes from a,c without r = 1

    x = a/nor =  p \times h^2

    y= b/nmr = q^3

    u= c/mor = g^3 \times k \times l

    the product of rmnoxyu is [a,b,c]

    what I did was covering all the possibilities for the primes and I avoid to repeat anyone of them

    this idea came to my head from the picture that I painted it is like sets
    but here the union of two sets (consider a,b,c sets containing prime number ) for example

    a union b = [a,b] = ab/(a,b) but in sets (a union b = a+b - a intersect b)

    (a,b) is the intersection

    and

    a union b union c = [a,b,c] since it contains all the primes without taking the same prime from two different set more than once

    is there anything is not clear


    Remark: in sets element repeated is not allowed but here there is a repeated elements
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    No, thats fantastic. The example made it much clearer. Thank you very much for your help
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by harkapobi View Post
    No, thats fantastic. The example made it much clearer. Thank you very much for your help

    That gives me great pleasure . . .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 25th 2011, 08:15 AM
  2. Connecting f, f', and f''.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 12th 2010, 04:41 PM
  3. set of odd integers proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 25th 2010, 09:21 AM
  4. Triangles connecting a box to a cylinder
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 2nd 2009, 08:55 PM
  5. Integers and proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 18th 2009, 09:39 AM

Search Tags


/mathhelpforum @mathhelpforum