# Least Common Multiple (LCM)

## 関連する計算機: 最小公倍数（LCM）計算機

Suppose we are given two numbers 18 and 24.

Let's find some of their multiples.

18: 18,36,54,72,90,108,126,144,...

24: 24,48,72,96,120,144,168,...

As can be seen some factors are same for both numbers (they are in bold: 72 and 144). These numbers are called common multiples of 18 and 24.

The smallest of common multiples (in bold red) is called the least common multiple.

For any integer numbers ${a}$ and ${b}$ we can find least common multiple.

It is denoted by ${L}{C}{M}{\left({a},{b}\right)}$ (short for the Least Common Multiple).

Let's see how to find least common multiple.

To find the Least Common Multiple of ${a}$ and ${b}$ find prime factorization of ${a}$ and ${b}$ and then take product of common factors taking each of them with greatest exponent.

Example 1. Find LCM(108,72).

Find prime factorization: ${108}={{2}}^{{2}}\cdot{{3}}^{{3}}$ and ${{2}}^{{3}}\cdot{{3}}^{{2}}$.

 108 72 Greater Factor Factor 2 ${{2}}^{{2}}$ ${{2}}^{{3}}$ ${{2}}^{{3}}$ Factor 3 ${{3}}^{{3}}$ ${{3}}^{{2}}$ ${{3}}^{{3}}$

So, ${L}{C}{M}{\left({108},{72}\right)}={{2}}^{{3}}\cdot{{3}}^{{3}}={8}\cdot{27}={216}$.

Next example.

Example 2. Find LCM(144,54).

Since ${144}={{2}}^{{4}}\cdot{{3}}^{{2}}$ and ${54}={{2}}^{{1}}\cdot{{3}}^{{3}}$ we see that common factors are 2 and 3.

 144 54 Greater Factor Factor 2 ${{2}}^{{4}}$ ${{2}}^{{1}}$ ${{2}}^{{4}}$ Factor 3 ${{3}}^{{2}}$ ${{3}}^{{3}}$ ${{3}}^{{3}}$

Therefore, ${L}{C}{M}{\left({144},{54}\right)}={{2}}^{{4}}\cdot{{3}}^{{3}}={432}$.

Next example.

Example 3. Find LCM(3780,7056).

Find prime factorization: ${3780}={{2}}^{{2}}\cdot{{3}}^{{3}}\cdot{5}\cdot{7}$ and ${7056}={{2}}^{{4}}\cdot{{3}}^{{2}}\cdot{{7}}^{{2}}$.

You can see that 7056 doesn't have 5 as factor, while 3780 has.

We can write in prime factorization of 7056 factor ${{5}}^{{0}}$ because ${{5}}^{{0}}={1}$: ${7056}={{2}}^{{4}}\cdot{{3}}^{{2}}\cdot{{5}}^{{0}}\cdot{{7}}^{{2}}$.

 3780 7056 Greater Factor Factor 2 ${{2}}^{{2}}$ ${{2}}^{{4}}$ ${{2}}^{{4}}$ Factor 3 ${{3}}^{{3}}$ ${{3}}^{{2}}$ ${{3}}^{{3}}$ Factor 5 ${{5}}^{{1}}$ ${{5}}^{{0}}$ ${{5}}^{{1}}$ Factor 7 ${{7}}^{{1}}$ ${{7}}^{{2}}$ ${{7}}^{{2}}$

So, ${L}{C}{M}{\left({3780},{7056}\right)}={{2}}^{{4}}\cdot{{3}}^{{3}}\cdot{{5}}^{{1}}\cdot{{7}}^{{2}}={105840}$.

Now, take pen and paper and do following exercises.

Exercise 1. Find LCM(45,375).

Next exercise.

Exercise 2. Find LCM(63,450).

Fact. ${G}{C}{D}{\left({a},{b}\right)}\cdot{L}{C}{M}{\left({a},{b}\right)}={a}{b}$.
In particular, it means that if a and b are relatively prime $\left({G}{C}{D}{\left({a},{b}\right)}={1}\right)$ then ${L}{C}{M}{\left({a},{b}\right)}={a}{b}$.