# Math Help - gcd and lcm

1. ## 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?

2. Originally Posted by Sampras
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$.

3. Originally Posted by Sampras
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.$

4. Originally Posted by ThePerfectHacker
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.

5. Originally Posted by Sampras
$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.

6. Originally Posted by TheAbstractionist
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$?

7. Originally Posted by Sampras
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.