Results 1 to 7 of 7

Math Help - gcd and lcm

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    gcd and lcm

    Show that if  a >0, \ b >0 then  ab = \gcd(a,b) \cdot \text{lcm}(a,b) .

    So factor  a and  b into a product of primes. Let  A be the set of primes that when multiplied, give  a . Let  B be defined similarly. So then if we look at  A \cup B and  A \cap B , we get the desired result?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Sampras View Post
    Show that if  a >0, \ b >0 then  ab = \gcd(a,b) \cdot \text{lcm}(a,b) .

    So factor  a and  b into a product of primes. Let  A be the set of primes that when multiplied, give  a . Let  B be defined similarly. So then if we look at  A \cup B and  A \cap B , we get the desired result?
    Write a=\prod p_i^{c_i} and b=\prod p_i^{d_i} then \gcd(a,b) = \prod p^{\text{min}(c_i,d_i)} and \text{lcm}(a,b) = \prod p^{\text{max}(c_i,d_i)}.
    Now compare both hands and show they are equal since \text{min}(c_i,d_i) + \text{max}(c_i,d_i) = c_i + d_i.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Sampras View Post
    Show that if  a >0, \ b >0 then  ab = \gcd(a,b) \cdot \text{lcm}(a,b) .
    Hi Sampras.

    Consider first the case when \gcd(a,b)=1. Since a\mid ab and b\mid ab, we have \mathrm{lcm}(a,b)\mid ab. Let \mathrm{lcm}(a,b)=aa'=bb'. Then, since \gcd(a,b)=1, we have a\mid b'.\ \therefore\ ab\mid bb'=\mathrm{lcm}(a,b). This proves that \mathrm{lcm}(a,b)=ab when \gcd(a,b)=1.

    If \gcd(a,b)=d, let a=a''d and b=b''d. Then \gcd(a'',b'')=1 and so \mathrm{lcm}(a'',b'')=a''b''. Then \mathrm{lcm}(a,b)=d\cdot\mathrm{lcm}(a'',b'')=a''b  '' and hence \gcd(a,b)\cdot\mathrm{lcm}(a,b)=(a''d)(b''d)=ab.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by ThePerfectHacker View Post
    Write a=\prod p_i^{c_i} and b=\prod p_i^{d_i} then \gcd(a,b) = \prod p^{\text{min}(c_i,d_i)} and \text{lcm}(a,b) = \prod p^{\text{max}(c_i,d_i)}.
    Now compare both hands and show they are equal since \text{min}(c_i,d_i) + \text{max}(c_i,d_i) = c_i + d_i.
     p are the primes that are common to both  a and  b ? Because here there is no subscript.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Sampras View Post
     p are the primes that are common to both  a and  b ? Because here there is no subscript.
    Okay, think of it as a=\prod_{i=1}^{\infty}p_i^{c_i} where \{p_1,p_2,p_3,...\} are the prime numbers. This infinite product is really finite because all c_i=0 except for finitely many. For example, 140 = 2^2 \cdot 3^0 \cdot 5^1 \cdot 7^1 \cdot 11^0 \cdot 13^0 \cdot ... . Thus, they share the exact same primes with just a possible exponent of zero.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by TheAbstractionist View Post
    Hi Sampras.

    Consider first the case when \gcd(a,b)=1. Since a\mid ab and b\mid ab, we have \mathrm{lcm}(a,b)\mid ab. Let \mathrm{lcm}(a,b)=aa'=bb'. Then, since \gcd(a,b)=1, we have a\mid b'.\ \therefore\ ab\mid bb'=\mathrm{lcm}(a,b). This proves that \mathrm{lcm}(a,b)=ab when \gcd(a,b)=1.

    If \gcd(a,b)=d, let a=a''d and b=b''d. Then \gcd(a'',b'')=1 and so \mathrm{lcm}(a'',b'')=a''b''. Then \mathrm{lcm}(a,b)=d\cdot\mathrm{lcm}(a'',b'')=a''b  '' and hence \gcd(a,b)\cdot\mathrm{lcm}(a,b)=(a''d)(b''d)=ab.
    How do we know that  \text{lcm}(a,b)|ab ? We know that  ab= ak = bj for  k, j \in \mathbb{Z} . But how does this imply that  aa' = bb' = \text{lcm}(a,b) | ab ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Sampras View Post
    How do we know that  \text{lcm}(a,b)|ab ? We know that  ab= ak = bj for  k, j \in \mathbb{Z} . But how does this imply that  aa' = bb' = \text{lcm}(a,b) | ab ?
    What’s the definition of LCM?

    Definition: The LCM of a and b is the number L with the property that

    .(i) a,\,b\mid L
    (ii) for any M, if a,\,b\mid M, then L\mid M.

    Since a,b\mid ab,\ \mathrm{lcm}(a,b)\mid ab by definition.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum