## 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

STAY CONNECTED