Lowest Common Multiple

Go back to  'Arithmetic-Integers'

The lowest common multiple (abbreviated as LCM) of two natural numbers x and y is the smallest natural number which is a multiple of both x and y, that is, of which x and y are both factors. For example, the LCM of

• 3 and 7 is 21, that is, LCM(3,7) = 21

• 18 and 24 is 72, that is, LCM(18,24) = 72

• 60 and 90 is 180, that is, LCM(60,90) = 180

• 10 and 17 is 170, that is, LCM(10,17) = 170

Given any two numbers, how can we find out their LCM? Consider the pair of numbers 24 and 60. Let us write the prime factorization of each:

\begin{align}&24 = {2^3} \times {3^1}\\&60 = {2^2} \times {3^1} \times {5^1}\end{align}

Since the LCM must be a multiple of both these numbers, it must contain all the prime factors occurring in these numbers. For example, the LCM of 24 and 60 must contain 2 as a factor. But how many factors of 2 should it contain? Note that there are three factors of 2 in 24, and two factors of 2 in 60. Since the LCM is a multiple of both numbers, it must contain three factors of 2 (it should not contain any more factors of 2 since we are looking for the lowest common multiple). Similarly, the LCM must contain one factor of 3 and one factor of 5. Thus:

${\rm{LCM}}\left( {24,\;60} \right) = {2^3} \times {3^1} \times {5^1}\, = 120$

Let us take another example. Find the LCM of 840 and 79200. The prime factorization of the two numbers will be:

\begin{align}&\;\;\;\;840 = {2^3} \times {3^1} \times {5^1} \times {7^1}\\&79200 = {2^5} \times {3^2} \times {5^2} \times {11^1}\end{align}

The LCM of the two numbers will be the product of the greatest power of each prime factor occurring in both the numbers:

\begin{align}&{\rm{LCM}}\left( {840,\;79200} \right) = {2^5} \times {3^2} \times {5^2} \times {7^1} \times {11^1}\\&\qquad\qquad\qquad\qquad= 554400\end{align}

Example 1: Find the HCF and LCM of 980 and 9000.

Solution: First, we carry out the prime factorization of the two numbers:

$\begin{array}{*{20}{l}}2 \vert {980}\\\hline2 \vert {490}\\\hline5 \vert {245}\\\hline7 \vert {49}\\\hline7 \vert 7\\\hline{\;\;} \vert 1\end{array} \begin{array}{*{20}{l}}2 \vert {9000}\\\hline2 \vert {4500}\\\hline2 \vert {2250}\\\hline3 \vert {1125}\\\hline3 \vert {375}\\\hline5 \vert {125}\\\hline5 \vert {25}\\\hline5 \vert 5\\\hline{\;\;} \vert 1\end{array}$

Thus:

\begin{align}&\;\;980 = {2^2} \times {5^1} \times {7^2}\\&9000 = {2^3} \times {3^2} \times {5^3}\end{align}

Finally,

\begin{align}&{\rm{HCF}}\left( {980,\;9000} \right)\; = {2^2} \times {5^1}\\& \qquad\qquad\qquad\quad \;\; = 20\\&{\rm{LCM}}\left( {980,\;9000} \right) = {2^3} \times {3^2} \times {5^3} \times {7^2}\\ &\qquad\qquad\qquad\quad\;\;= 441000\end{align}

Example 2: Here is another similar example. Find the HCF and LCM of 371250 and 29040.

Solution: Once again, we carry out the prime factorization of the two numbers:

$\begin{array}{*{20}{l}}\;\;2\;\;\vert \;\;{371250}\\\hline\;\;3\;\;\vert \;\;{185625}\\\hline\;\;3\;\;\vert \;\;{61875}\\\hline\;\;3\;\;\vert \;\;{20625}\\\hline\;\;5\;\;\vert\;\; {6875}\\\hline\;\;5\;\;\vert \;\;{1375}\\\hline\;\;5\;\;\vert \;\;{275}\\\hline\;\;5\;\;\vert\;\; {55}\\\hline\;\;{11}\vert {11}\\\hline\;\;{\;\;\;\,}\vert \;\;1\end{array} \begin{array}{*{20}{l}}\;\;2\;\;\vert \;\;{29040}\\\hline\;\;2\;\;\vert\;\; {14520}\\\hline\;\;2\;\;\vert {7260}\\\hline\;\;2\;\;\vert \;\;{3630}\\\hline\;\;3\;\;\vert \;\;{1815}\\\hline\;\;5\;\;\vert {605}\\\hline{11}\;\;\vert \;\;{121}\\\hline\;\;{11}\vert {11}\\\hline{\;\;\;\;\;\,}\vert \;\;\;1\end{array}$

Thus:   \begin{align}&371250 = {2^1} \times {3^3} \times {5^4} \times {11^1}\\&\;\,29040 = {2^4} \times {3^1} \times {5^1} \times {11^2}\end{align}

Now, we can calculate the HCF and LCM:

\begin{align}&{\rm{HCF}}\left( {371250,\;29040} \right) = {2^1} \times {3^1} \times {5^1} \times {11^1}\\& \qquad\qquad\qquad\qquad\quad\;= 330\\&{\rm{LCM}}\left( {371250,\;29040} \right) = {2^4} \times {3^3} \times {5^4} \times {11^2}\\ &\qquad\qquad\qquad\qquad\quad\;= 32670000\end{align}

Example 3: Determine the relation between the HCF and LCM of two numbers x and y.

Solution:. Recall that once we divide each of a pair of numbers by their HCF, the resulting numbers have no factors in common, since all the common factors have been taken out in the HCF. Consider the following relations:

\begin{align}&x = {\rm{HCF}} \times a\\&y = {\rm{HCF}} \times b\end{align}

That is, we have written each of x and y as a product of their HCF and another number. Clearly, a and b will have no factors in common.

Now, think about the LCM of x and y. It should be a multiple of both x and y. Obviously, it should have the HCF as a factor, but it should also have a and b as factors. That is, the LCM should be divisible by: the HCF, a and b. Only then can it be a multiple of both x and y. A little more thinking will show that the LCM will be:

${\rm{LCM}} = {\rm{HCF}} \times a \times b$

This product is the lowest possible number which will be a common multiple of both x and y, and so it is the LCM. Convince yourself about this. If you have difficulty understanding this, work with a couple of concrete examples.

Now:

\begin{align}&x\times y = \left( {{\rm{HCF}} \times a} \right) \times \left( {{\rm{HCF}} \times b} \right)\\&\qquad= {\rm{HCF}} \times \left( {{\rm{HCF}} \times a \times b} \right)\\&\qquad = {\rm{HCF}} \times {\rm{LCM}}\end{align}

Thus, the product of the HCF and LCM of two numbers x and y is the product of x and y. This means that if we have the HCF of two numbers, we can evaluate the LCM directly, and vice-versa:

\begin{align}&{\rm{LCM}}\left( {x,\;y} \right) = \frac{{x \times y}}{{{\rm{HCF}}\left( {x,\;y} \right)}}\\&{\rm{HCF}}\left( {x,y} \right) = \frac{{x \times y}}{{{\rm{LCM}}\left( {x,y} \right)}}\end{align}

As an example, consider the numbers 24 and 60. Their HCF is 12, and so:

\begin{align}&{\rm{LCM}}\left( {24,\;60} \right) = \frac{{24 \times 60}}{{{\rm{HCF}}\left( {24,\;60} \right)}}\\& \qquad\qquad\qquad= \frac{{24 \times 60}}{{12}}\\& \qquad\qquad\qquad = 120\end{align}

Example 4: Find the HCF and LCM of the three numbers 168, 252 and 288.

Solution: We prime factorize the three numbers first. Verify that we will obtain the following:

\begin{align}&168 = {2^3} \times {3^1} \times {7^1}\\&252 = {2^2} \times {3^2} \times {7^1}\\&288 = {2^5} \times {3^2}\end{align}

The HCF of these numbers will be the product of the smallest power of each common prime factor in the numbers:

\begin{align}&{\rm{HCF}}\left( {168,\;252,\;288} \right) = {2^2} \times {3^1}\\& \qquad\qquad\qquad\qquad \quad= 12\end{align}

The LCM will be the product of the greatest power of each prime factor occurring in the three numbers:

\begin{align}&{\rm{LCM}}\left( {168,\;252,\;288} \right) = {2^5} \times {3^2} \times {7^1}\\ &\qquad\qquad\qquad\qquad\quad = 2016\end{align}

Note that in this case, the product of the HCF and LCM of the three numbers will not be equal to the product of the three numbers. Can you see why?

Example 5: Consider the number 4n, where n is a natural number. Can the last digit of this number be 0 for any value of n?

Solution: For the last digit of a number to be 0, it must be a multiple of 10, that is, it must have 2 and 5 as factors. But a number of the form 4n will only have 2 as a prime factor, since its prime factorization will be:

${4^n} = {\left( {{2^2}} \right)^n} = {2^{2n}}$

Thus, such a number will not have 5 as a factor, which means that its last digit cannot be 0.

Learn math from the experts and clarify doubts instantly

• Instant doubt clearing (live one on one)
• Learn from India’s best math teachers
• Completely personalized curriculum