How do you find the least common multiple between two numbers?

Saturday, May 15, 2010

How do you find the least common multiple between two numbers?

Hello!

Suppose that the two numbers are both >=2 (if one of the numbers is 1, the problem is trivial). Then both have its unique decomposition into prime factors. If we find this decomposition, which is not simple for large numbers, then LCM must contain the maximum degrees of all prime factors from both numbers.

Consider an example. Let $\displaystyle{a}={126},$ $\displaystyle{b}={108}.$ Then $\displaystyle{a}={{2}}^{{1}}\cdot{{3}}^{{2}}\cdot{7},$ $\displaystyle{b}={{2}}^{{2}}\cdot{{3}}^{{3}}.$ The maximum degrees are $\displaystyle{2}$ for $\displaystyle{2},$ $\displaystyle{3}$ for $\displaystyle{3}$ and $\displaystyle{1}$ for $\displaystyle{7}.$ Hence $\displaystyle{L}{C}{M}{\left({a},{b}\right)}={{2}}^{{2}}\cdot{{3}}^{{3}}\cdot{7}={756}.$

Another method is to find the greatest common divisor (for example, using Euclidean algorithm) and use the fact that $\displaystyle{a}\cdot{b}={L}{C}{M}{\left({a},{b}\right)}\cdot{G}{C}{D}{\left({a},{b}\right)}.$