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

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

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

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

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

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

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