Results 1 to 7 of 7

Thread: gcd and lcm

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

    gcd and lcm

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

    So factor $\displaystyle a $ and $\displaystyle b $ into a product of primes. Let $\displaystyle A $ be the set of primes that when multiplied, give $\displaystyle a $. Let $\displaystyle B $ be defined similarly. So then if we look at $\displaystyle A \cup B $ and $\displaystyle 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
    10
    Quote Originally Posted by Sampras View Post
    Show that if $\displaystyle a >0, \ b >0 $ then $\displaystyle ab = \gcd(a,b) \cdot \text{lcm}(a,b) $.

    So factor $\displaystyle a $ and $\displaystyle b $ into a product of primes. Let $\displaystyle A $ be the set of primes that when multiplied, give $\displaystyle a $. Let $\displaystyle B $ be defined similarly. So then if we look at $\displaystyle A \cup B $ and $\displaystyle A \cap B $, we get the desired result?
    Write $\displaystyle a=\prod p_i^{c_i}$ and $\displaystyle b=\prod p_i^{d_i}$ then $\displaystyle \gcd(a,b) = \prod p^{\text{min}(c_i,d_i)}$ and $\displaystyle \text{lcm}(a,b) = \prod p^{\text{max}(c_i,d_i)}$.
    Now compare both hands and show they are equal since $\displaystyle \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 $\displaystyle a >0, \ b >0 $ then $\displaystyle ab = \gcd(a,b) \cdot \text{lcm}(a,b) $.
    Hi Sampras.

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

    If $\displaystyle \gcd(a,b)=d,$ let $\displaystyle a=a''d$ and $\displaystyle b=b''d.$ Then $\displaystyle \gcd(a'',b'')=1$ and so $\displaystyle \mathrm{lcm}(a'',b'')=a''b''.$ Then $\displaystyle \mathrm{lcm}(a,b)=d\cdot\mathrm{lcm}(a'',b'')=a''b ''$ and hence $\displaystyle \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 $\displaystyle a=\prod p_i^{c_i}$ and $\displaystyle b=\prod p_i^{d_i}$ then $\displaystyle \gcd(a,b) = \prod p^{\text{min}(c_i,d_i)}$ and $\displaystyle \text{lcm}(a,b) = \prod p^{\text{max}(c_i,d_i)}$.
    Now compare both hands and show they are equal since $\displaystyle \text{min}(c_i,d_i) + \text{max}(c_i,d_i) = c_i + d_i$.
    $\displaystyle p $ are the primes that are common to both $\displaystyle a $ and $\displaystyle 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
    10
    Quote Originally Posted by Sampras View Post
    $\displaystyle p $ are the primes that are common to both $\displaystyle a $ and $\displaystyle b $? Because here there is no subscript.
    Okay, think of it as $\displaystyle a=\prod_{i=1}^{\infty}p_i^{c_i}$ where $\displaystyle \{p_1,p_2,p_3,...\}$ are the prime numbers. This infinite product is really finite because all $\displaystyle c_i=0$ except for finitely many. For example, $\displaystyle 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 $\displaystyle \gcd(a,b)=1.$ Since $\displaystyle a\mid ab$ and $\displaystyle b\mid ab,$ we have $\displaystyle \mathrm{lcm}(a,b)\mid ab.$ Let $\displaystyle \mathrm{lcm}(a,b)=aa'=bb'.$ Then, since $\displaystyle \gcd(a,b)=1,$ we have $\displaystyle a\mid b'.\ \therefore\ ab\mid bb'=\mathrm{lcm}(a,b).$ This proves that $\displaystyle \mathrm{lcm}(a,b)=ab$ when $\displaystyle \gcd(a,b)=1.$

    If $\displaystyle \gcd(a,b)=d,$ let $\displaystyle a=a''d$ and $\displaystyle b=b''d.$ Then $\displaystyle \gcd(a'',b'')=1$ and so $\displaystyle \mathrm{lcm}(a'',b'')=a''b''.$ Then $\displaystyle \mathrm{lcm}(a,b)=d\cdot\mathrm{lcm}(a'',b'')=a''b ''$ and hence $\displaystyle \gcd(a,b)\cdot\mathrm{lcm}(a,b)=(a''d)(b''d)=ab.$
    How do we know that $\displaystyle \text{lcm}(a,b)|ab $? We know that $\displaystyle ab= ak = bj $ for $\displaystyle k, j \in \mathbb{Z} $. But how does this imply that $\displaystyle 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 $\displaystyle \text{lcm}(a,b)|ab $? We know that $\displaystyle ab= ak = bj $ for $\displaystyle k, j \in \mathbb{Z} $. But how does this imply that $\displaystyle aa' = bb' = \text{lcm}(a,b) | ab $?
    What’s the definition of LCM?

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

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

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

Search Tags


/mathhelpforum @mathhelpforum