6
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ I take it that HCF is gcd? (Highest common factor; greatest common divisor?) $\endgroup$ – amWhy Jun 11 '11 at 21:42
  • 1
    $\begingroup$ Yes that's correct @amWhy! $\endgroup$ – peakit Jun 12 '11 at 3:36
10
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ This is an example of the "modular equation" $|A| + |B| = |A \cup B| + |A \cap B|$. $\endgroup$ – Yuval Filmus Jun 11 '11 at 21:35
  • 7
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Jun 11 '11 at 21:42
  • $\begingroup$ 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. $\endgroup$ – peakit Jun 12 '11 at 3:35
  • 3
    $\begingroup$ @peakit: to me, that sounds like exactly what I wrote. $\endgroup$ – Rasmus Jun 12 '11 at 9:47
13
$\begingroup$

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\ \ \ \ \ \ d\mid a,b \iff a,b\mid ab/d \iff [a,b]\mid ab/d \iff d\mid ab/[a,b] $

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – user43208 Oct 20 '13 at 16:18
3
$\begingroup$

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|$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 12 '11 at 13:11
  • $\begingroup$ @Gerry, sure, but I think this is a pretty easy consequence of $(ma,mb)=m(a,b)$ either way. $\endgroup$ – yunone Jun 12 '11 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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