Least common multiple (lcm) and Greatest common divisor (gcd) question: “Prove lcm(m,n) = m*n/gcd(m,n)?”

Answer

It’s equivalent to proving
m*n = (lcm(m,n) ) * ( gcd(m,n) )

Now, i’ll have to use basic number theory. The idea is to show that the number of times a prime factor of m*n occurs on the LHS is equal to the number of times a prime factor of (lcm(m,n) ) * ( gcd(m,n) ) occurs on the RHS.
Note : LHS = Left Hand Side
RHS = Right Hand Side

For any prime factor p of m*n, call it p. Now say p occurs to the power of h in m and power of k in n. That is to say m “contains” p^h while n contains p^k. Note that h,k are nonnegative integers.

Now, in lcm(m,n), we would choose p^ [ min(h,k) ] while
in gcd(m,n) we would choose p^ [ max(h,k) ]
Note that min (h,k) means minimum of h and k, similarly max (h,k)means maximum of h and k . For example, if h=2 and k=3, then min (2,3) = 2. while max(2,3) = 3. If say h = k, then obviously in both lcm and gcd of m*n we choose p^h to be in its product. This is true for EVERY prime factor of m*n.

So, consider the product (lcm(m,n) ) * ( gcd(m,n) ).
For EACH prime factor p of m*n, we have shown above that it occurs as { p^ [ min(h,k) ] } * { p^ [ max(h,k) ] }, that is our RHS product contains
p^ [ min(h,k) + max(h,k) ] = p^(h+k)
Now, in our LHS, p occurs as p^h * p^k = p^(h+k) too!!!
Thus, we have shown for each prime factor, p of m*n, it occurs as the same product in both the LHS and RHS. And thus
we have LHS = RHS. Done.

One question may circle in your mind, that is how i know that [ min(h,k) + max(h,k) ] = (h+k)
Well, this is a fact.

Further, if you want to show it, consider 3 cases.

Case 1. ( h = k)
Here min(h,k) = min(h,h) = h
and max(h,k) = max(h,h) = h
So, [ min(h,k) + max(h,k) ] = h + h = 2h.
And (h+k)= h + h = 2h.

Case 2. ( h < k)
Here min(h,k) = h, because h is smaller.
and max(h,k) = k, because k is bigger.
So, [ min(h,k) + max(h,k) ] = h + k

Case 3. ( h > k )
Here min(h,k) = k, because k is smaller.
and max(h,k) = h, because h is bigger.
So, [ min(h,k) + max(h,k) ] = k + h