Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 22, 2009 #1
    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.
     
  2. jcsd
  3. Jun 22, 2009 #2

    in3

    User Avatar

    If
    [tex]a = p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n}[/tex],

    [tex]b = p_1^{f_1} \cdot p_2^{f_2} \cdots p_n^{f_n}[/tex],

    where [tex]p_i[/tex] are unique prime numbers and [tex]e_i \ge 0, f_i \ge 0[/tex], then

    [tex]\text{hcf}(a,b) = p_1^{\min(e_1,f_1)} \cdots p_n^{\min(e_n, f_n)}[/tex],

    [tex]\text{lcm}(a,b) = p_1^{\max(e_1,f_1)} \cdots p_n^{\max(e_n, f_n)}[/tex].

    So what's [tex]\text{hcf}(a,b) \cdot \text{lcm}(a,b)[/tex]?
     
  4. Jun 24, 2009 #3
    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.
     
  5. Jun 24, 2009 #4

    in3

    User Avatar

    [tex]p_1, \ldots, p_n[/tex] are all the prime factors from both a and b. Note that if [tex]p_k[/tex] is a prime factor in a but not in b, then [tex]f_k[/tex] 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.
     
  6. Jun 24, 2009 #5
    [tex] hcf(a,b) [/tex] 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 [tex] p_n[/tex]'s, right? so whatever is smaller, thus [tex]min (e_n, f_n)[/tex], will become a common factor of a and b. if we multiply all of these we get [tex] hcf (a,b) [/tex]

    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

    [tex]12=2^2*3[/tex]
    [tex]120=2^3*3*5[/tex]
    [tex]hcf(12,120)=2^{min(2,3)}*3^{min(1,1)}*5^{min(0,1)}=2^2*3^1*5^0=12[/tex]
    [tex]lcm(12,120)=2^{max(2,3)}*3^{max(1,1)}*5^{max(0,1)}=2^3*3^1*5^1=120[/tex]
    [tex]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)[/tex]

    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 :)
     
    Last edited: Jun 24, 2009
  7. Jun 24, 2009 #6

    thrill3rnit3

    User Avatar
    Gold Member

    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 [tex]p[/tex]. It enters the factorization of [tex]a[/tex] as [tex]p^{e}[/tex] and of [tex]b[/tex] as [tex]p^{f}[/tex]. Without loss of generality let's say that [tex]a \leq b[/tex]. When we take the HCF of [tex]a[/tex] and [tex]b[/tex], we need [tex]e[/tex] number of [tex]p's[/tex], since any more factors of [tex]p[/tex] will not divide [tex]b[/tex]. Similarly, when we take the LCM, we need [tex]f[/tex] number of [tex]p's[/tex], since [tex]f[/tex] factors of [tex]p[/tex] are required if [tex]b[/tex] is to divide the LCM. Thus, in the product of the HCF and LCM all factors of [tex]p[/tex] will come together as [tex]p^{e+f}[/tex]. But this factor [tex]p^{e+f}[/tex] is the same power of [tex]p[/tex] which enters into the prime factorization of [tex]ab[/tex]!. Since this argument applies to any prime [tex]p[/tex], the prime factorizations of lcm(a,b)*hcf(a,b) and [tex]ab[/tex] must be the same, so lcm(a,b)*hcf(a,b) and [tex]ab[/tex] must be equal. Q.E.D.
     
  8. Jun 25, 2009 #7
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A*b = LCM(a,b)*HCF(a,b)
  1. Proof of lcm(a,b) (Replies: 1)

  2. AxB=B ? (Replies: 11)

Loading...