Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading a text book and came across the following:

Important Results
(This comes immediately after LCM:)

If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$ respectively,
then $L \times H = a \times b$

Can some please help me understand why the above result is true?

Thanks in advance.

share|improve this question
    
I take it that HCF is gcd? (Highest common factor; greatest common divisor?) –  amWhy Jun 11 '11 at 21:42
1  
Yes that's correct @amWhy! –  peakit Jun 12 '11 at 3:36
add comment

3 Answers

up vote 6 down vote accepted

Let $p$ be a prime. If $p$ occurs in $a$ with multiplicity $m$ and in $b$ with multiplicity $n$, then it will occur in the LCM of $a$ and $b$ with multiplicity $\mathrm{max(m,n)}$ and in their HCF with multiplicity $\mathrm{min(m,n)}$.

Hence, in the product of LCM and HCF the multiplicity of $p$ is $$\mathrm{max}(m,n)+\mathrm{min}(m,n)=m+n,$$ which is also the multiplicity of $p$ in $a\cdot b$. Since this holds for every $p$, the two products must be equal.

share|improve this answer
1  
This is an example of the "modular equation" $|A| + |B| = |A \cup B| + |A \cap B|$. –  Yuval Filmus Jun 11 '11 at 21:35
4  
But this assumes $p$ occurs with a well-defined multiplicity in $a$ and $b$, which is to say it assumes unique factorization. Has the text already done unique factorization when it introduces LCM? –  Gerry Myerson Jun 11 '11 at 21:42
    
Thanks @Ramsus, your answer helped a lot! Another way to logically deduce this is: LCM of 2 numbers will cover the max multiplicity for each of the prime factors, but HCF will cover the min multiplicity for each of the prime factors and simple multiplication covers 'sum' of multiplicity of the prime factor which is same as LCM multiplied by HCF. –  peakit Jun 12 '11 at 3:35
2  
@peakit: to me, that sounds like exactly what I wrote. –  Rasmus Jun 12 '11 at 9:47
add comment

Below is a proof that works in any domain, using the universal definitions of GCD, LCM.

THEOREM $\rm\quad (a,b)\ =\ ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof: $\rm\qquad d\mid (a,b)\iff d\mid a,b \iff a,b\mid ab/d \iff [a,b]\mid ab/d \iff d\mid ab/[a,b] $

share|improve this answer
    
User is "Gone" but the proof is excellent. It's too bad this wasn't the accepted answer, in view of its generality and Gerry Myerson's apt comment below the accepted answer. –  user43208 Oct 20 '13 at 16:18
add comment

You can also figure this out without using any use of unique factorization. Since you say this comes immediately after LCM, I assume you know that for $m\gt 0$, $[ma,mb]=m[a,b]$, where $[a,b]=\mathrm{lcm}(a,b)$ and $(ma,mb)=m(a,b)$ where $\gcd(a,b)=(a,b)$.

Now suppose $(a,b)=1$, and also assume they are positive, since if they are negative $[a,-b]=[a,b]$ anyway. Since $[a,b]$ is some multiple of $a$, let $[a,b]=ma$. Then $b\mid ma$, but $(a,b)=1$, so $b\mid m$. If this hasn't be addressed yet, notice $(ma,mb)=m(a,b)=m$, so $b\mid ma$, and $b\mid mb$, so $b\mid m$ since any common divisor of $ma$ and $mb$ divides the greatest common divisor $m$ in this case.

So $b\leq m$ as they are both positive, which implies $ba\leq ma$. But $ba$ is a common multiple of $a$ and $b$, so cannot be strictly less than $ma$, so $ba=ma=[a,b]$.

More generally, if $(a,b)=g\gt 1$, then you have $(\frac{a}{g},\frac{b}{g})=1$. Then by the special case above, $$ \left[\frac{a}{g},\frac{b}{g}\right]\left(\frac{a}{g},\frac{b}{g}\right)=\frac{a}{g}\frac{b}{g}. $$ Multiply through by $g^2$, you have $$ \begin{align*} g^2\left[\frac{a}{g},\frac{b}{g}\right]\left(\frac{a}{g},\frac{b}{g}\right) &= g\left[\frac{a}{g},\frac{b}{g}\right]g\left(\frac{a}{g},\frac{b}{g}\right)\\ &= [a,b](a,b)\\ &= g^2\frac{a}{g}\frac{b}{g}=ab \end{align*} $$ so $[a,b](a,b)=|ab|$.

share|improve this answer
    
I suppose this doesn't use unique factorization, but it does use $b\mid ma$, $\gcd(a,b)=1$ implies $b\mid m$, which may or may not have been done by the text at this point. –  Gerry Myerson Jun 12 '11 at 13:11
    
@Gerry, sure, but I think this is a pretty easy consequence of $(ma,mb)=m(a,b)$ either way. –  yunone Jun 12 '11 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.