ab = LCM(a,b)HCF(a,b)

**Anonymus1984** · Jun22-09, 01:21 PM

Hello,

I have been searching in vain for a general proof of the following:

a*b = LCM(a,b)*HCF(a,b)

Please send me a link of please give me the proof. Or at least, please help me visualize how this comes about... I know it is true... but I'm just not able to visualize it...

I go up to seeing the product of the two numbers as the product of their respective prime factors and that contains the HCF of the Two numbers. But, I'm unable to visualize the rest of the prime factors together becoming the LCM of the two numbers.... please help me...

Thank you.

**in3** · Jun22-09, 03:01 PM

If
$LaTeX Code: a = p_1^{e_1} \\cdot p_2^{e_2} \\cdots p_n^{e_n}$ ,

$LaTeX Code: b = p_1^{f_1} \\cdot p_2^{f_2} \\cdots p_n^{f_n}$ ,

where

are unique prime numbers and $LaTeX Code: e_i \\ge 0, f_i \\ge 0$ , then

$LaTeX Code: \\text{hcf}(a,b) = p_1^{\\min(e_1,f_1)} \\cdots p_n^{\\min(e_n, f_n)}$ ,

$LaTeX Code: \\text{lcm}(a,b) = p_1^{\\max(e_1,f_1)} \\cdots p_n^{\\max(e_n, f_n)}$ .

So what's $LaTeX Code: \\text{hcf}(a,b) \\cdot \\text{lcm}(a,b)$ ?

**Anonymus1984** · Jun24-09, 10:46 AM

Hello in3,

Thanks for the reply. But, I still don't understand... I'm just a beginner.

Not all the Ps would be in the lcm(a,b) or the hcf(a,b) right? we take only the ones that are common.. right?

Also, I don't understand the representation of lcm and hcf... can you please send me a link where I can get a more detailed explanation of the representation?

Thank you.

**in3** · Jun24-09, 06:57 PM

$LaTeX Code: p_1, \\ldots, p_n$ are all the prime factors from both a and b. Note that if

is a prime factor in a but not in b, then

will be 0.

As for a link, I guess you could look at MathWorld, though I'm not sure it includes the details you seek. But I would encourage you to think about what hcf and lcm means and how it's reflected in the above.

**albert1993** · Jun24-09, 10:52 PM

Originally Posted by Anonymus1984

Hello in3,

Thanks for the reply. But, I still don't understand... I'm just a beginner.

Not all the Ps would be in the lcm(a,b) or the hcf(a,b) right? we take only the ones that are common.. right?

Also, I don't understand the representation of lcm and hcf... can you please send me a link where I can get a more detailed explanation of the representation?

Thank you.

is going to be all the common factors of a and b right?
so if we make a and b in the form that in3 made, we find that they share some

's, right? so whatever is smaller, thus

, will become a common factor of a and b. if we multiply all of these we get

and there will be enough p's in the lcm and hcf when multiplied because you're taking the minimum of p's in hcf and the maximum of p's in lcm.

here's a quick example: 12 & 120

$LaTeX Code: hcf(12,120)=2^{min(2,3)}*3^{min(1,1)}*5^{min(0,1)} =2^2*3^1*5^0=12$
$LaTeX Code: lcm(12,120)=2^{max(2,3)}*3^{max(1,1)}*5^{max(0,1)} =2^3*3^1*5^1=120$
$LaTeX Code: 12*120=2^2*3*2^3*3*5=2^{2+3}*3^{1+1}*5{0+1}=2^5*3^ 2*5=1440=12*120=lcm(12,120)*hcf(12,120)$

see that we added the exponents of each prime? that's multiplication of the two numbers a,b.
see that the minimum of the exponents and maximum of the exponents added together cover this up? that's hcf*lcm.

hope i helped :)

**thrill3rnit3** · Jun24-09, 11:13 PM

Here's a pretty informal explanation, but you should be able to visualize it from here.

So we're trying to prove that lcm(a,b)*hcf(a,b)=a*b. Consider any prime

. It enters the factorization of

as $LaTeX Code: p^{e}$ and of

as $LaTeX Code: p^{f}$ . Without loss of generality let's say that $LaTeX Code: a \\leq b$ . When we take the HCF of

and

, we need

number of

, since any more factors of

will not divide

. Similarly, when we take the LCM, we need

number of

, since

factors of

are required if

is to divide the LCM. Thus, in the product of the HCF and LCM all factors of

will come together as $LaTeX Code: p^{e+f}$ . But this factor $LaTeX Code: p^{e+f}$ is the same power of

which enters into the prime factorization of

!. Since this argument applies to any prime

, the prime factorizations of lcm(a,b)*hcf(a,b) and

must be the same, so lcm(a,b)*hcf(a,b) and

must be equal. Q.E.D.

**Anonymus1984** · Jun25-09, 10:32 AM

I understand now... thank you in3, albert1993 and thrill3rnit3...

Once you understand something, it looks so simple and you wonder why you didn't get it all along... I guess that is the sign of understanding something...

Thank you very much.