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

  • 1
    I take it that HCF is gcd? (Highest common factor; greatest common divisor?)2011-06-11
  • 1
    Yes that's correct @amWhy!2011-06-12

3 Answers 3

2

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

  • 0
    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.2011-06-12
  • 0
    @Gerry, sure, but I think this is a pretty easy consequence of $(ma,mb)=m(a,b)$ either way.2011-06-12
11

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

  • 1
    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.2013-10-20
9

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.

  • 2
    This is an example of the "modular equation" $|A| + |B| = |A \cup B| + |A \cap B|$.2011-06-11
  • 7
    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?2011-06-11
  • 0
    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.2011-06-12
  • 3
    @peakit: to me, that sounds like exactly what I wrote.2011-06-12