HCF and LCM

What are HCF and LCM and how they are used

The highest factor common to a set of numbers

Highest Common Factor or HCF is the largest factor that divides two or more numbers. It is the largest among all the factors common to the set of numbers under consideration.

For example, the factors of the three numbers, 12, 30 and 42 are,

$12 = 2\times{2}\times{3}$,

$30 = 2\times{3}\times{5}$, and

$42 = 2\times{3}\times{7}$.

The factors common to the three numbers are 2 and 3. These are the prime common factors. Multiplying these we get 6 as the HCF of the three numbers 12, 30 and 42.

Finding HCF

There are two methods of finding the HCF of a set of given numbers. We have seen the first method of factorization of the given numbers, visually identifying the common prime factors and multiplying these to get the HCF. Still we are repeating the first method.

Factorization method for finding HCF

We will find the HCF of 36, 54, 126 and 180 by factorization. As we are well conversant with factorization of small numbers we are able to break the four numbers into their factors in no time,

$36 = 2\times{2}\times{3}\times{3}$.

$54 = 2\times{3}\times{3}\times{3}$.

$126 = 2\times{3}\times{3}\times{7}$.

$180 = 2\times{2}\times{3}\times{3}\times{5}$.

On careful inspection we find that only one 2 as factor is common to all four numbers, but two numbers of 3 as factors are also common to the four given numbers.

So our HCF is,

$HCF = 2\times{3}\times{3} = 18$.

Euclid's algorithm of repeated division to find the HCF of a pair of integers

In the second method, HCF of two numbers are found by repeated division of the Divisor of the previous stage by the Remainder of the previous stage till the remainder becomes 0.

The last divisor turns out to be the HCF of two given numbers.

Example: to find HCF of 12 and 30

$ 30\div{12}=2\times{12} + 6$, Remainder is 6. In the next step, this remainder of 6 will act as the divisor and the divisor 12 in the previous stage will be the dividend.

$12\div{6} =2\times{6} + 0$, remainder is 0.

In the second division, remainder is 0. So the divisor 6 at this stage becomes the HCF of two numbers 12 and 30.

Pictorially, in general, it will be something like this,

And in our case of finding the HCF of 12 and 30, the method will be,

This is a very simple but intelligent method and it is due to no other person than legendary mathematician Euclid himself.

Recommendation:

Note that this second method can't deal with more than two numbers when finding the HCF; you have to find the HCF of any pair, and then find the HCF of the number resulting from the first operation and the next number in the original set and so on. But in any case this method is easy, and chances of error is less. When the number of numbers is less you should go in for this method.

When you are well conversant with quick mental factorization of numbers, you might opt for the factorization method which would be faster in that case.

Least Common Multiple or LCM

The LCM is the smallest number that is divisible by the set of given numbers. In other words, LCM is the least common multiple of the set of given numbers. To take our previous example of the three numbers 12, 30 and 42, the problem definition now is to find out the LCM of these three numbers.

Finding LCM by factorization

First we will find out the LCM of the numbers 12, 30 and 42 by factorization. The numbers broken in to their product of factor form are as before,

$12 = 2\times{2}\times{3}$,

$30 = 2\times{3}\times{5}$, and

$42 = 2\times{3}\times{7}$.

The technique here is to count the common factors only once. Here common factors $2\times{3}$ would be counted only once in forming the LCM. Then all the rest of the factors of the three numbers that are not common to the three numbers are to be considered in forming the LCM. By inspection we find these to be 2, 5 and 7.

So the LCM of the three numbers 12, 30 and 40 would be,

$2\times{3}\times{2}\times{5}\times{7} = 420 $

LCM by pairwise factorization

As $2\times{3}=6$ is the HCF of 12 and 30, the LCM of these two numbers would be found by multiplying 6 with the factors 2 and 5 that are not common to these two numbers.

Result would be, $6\times{2}\times{5}=60$. This the smallest multiple of 12 and 30. If we now consider the third number 42, we find that 6 is common with the new number, but a new factor 7 has come in. So by multiplying 60 by 7: $60\times{7}=420$ we would get the LCM of these three numbers 12, 30 and 42.

In this approach we have found out the LCM by considering pairs of numbers.

Finding LCM by a simple procedure

We would now show the simple procedure taught in schools for finding the LCM. In this procedure,

• All the numbers in the set are written in a row and the first divisor common to at least two of the numbers is written on the left of numbers. Below these numbers the quotient of divisions are written. If any of the numbers in the first row is not divisible by the divisor at this stage, that would appear in the second row unchanged.
• In the second stage, the quotients in the last row would be considered for dividing by a number common to at least two of these and the method same as in the first step would be followed.
• This process would be continued till there is no factor common to the last set of resultant numbers in the last row.
• LCM would be the product of all the dividing factors starting at the top left in the factor column and the remaining quotients in the last row of prime factors.

For example, finding LCM of 12, 30 and 42 would look like,

Recommendation:

The second method relies fully on a mechanical and easy procedure. You may select larger factors first to reduce the size of numbers as fast as possible. But remember, you have to find out the common prime factor at each step and also divide the numbers by the common factor. In any case you can't avoid this mental factorization process. In spite of this, all in all, if the numbers are larger in size and in number, you should use this simple procedure rather than factorization.

When you are used to quick factorization, and the numbers are not unknown or very large to you, you should go for the factorization method of finding LCM. As this method relies mostly on mental processes, it should be much faster when you are comfortable with the numbers.

Relation between HCF and LCM

From the nature of HCF and LCM of two numbers, it follows that the product of two numbers $n_{1}$ and $n_{2}$ is equal to the product of their HCF and LCM.

$ n_{1}\times{n_{2}}=HCF\times{LCM}$

For example, HCF and LCM of 12 and 30 are 6 and 60 respectively. Thus, by the above rule,

$12\times{30}=6\times{60}= 360 $

If any three of these four quantities of two numbers and their HCF and LCM are given, we can find out the fourth quantity.

---

Reason:

HCF consists of the common factors of the two numbers. In HCF the double occurrence of these common factors are taken once. On the other hand, in LCM not only the factors that are not common are taken but also the common factors are taken once. Thus multiplying HCF and LCM we cover the product of all the factors of the two numbers. This means product of HCF and LCM of two numbers always equals the product of the two numbers.

$12 = 2\times{2}\times{3}$,

$30 = 2\times{3}\times{5}$

In HCF factors 2 and 3 are taken into a product whereas in LCM the rest of the factors of the two numbers combined, 2, 5 and 2, 3 are taken to complete the whole set of factors of the two numbers combined.

---

We will now work out a few sums on HCF and LCM to give you a flavor of what type of problems can be there in this topic area and conclude the session with a set of carefully chosen problems as exercise.

Recommendation:

To be able to comfortably deal with the problems in this higher level concept area of HCF and LCM, we recommend strongly that you go throught our previous tutorials on Numbers and Number System and Factorization.

---

Example problems

Problem 1.

LCM of the fractions $\displaystyle\frac{2}{3}$, $\displaystyle\frac{4}{9}$ and $\displaystyle\frac{5}{6}$ is,

1. $\displaystyle\frac{8}{27}$
2. $\displaystyle\frac{20}{27}$
3. $\displaystyle\frac{10}{3}$
4. $\displaystyle\frac{20}{3}$

Solution:

To deal with fractions, be it addition, subtraction or HCF and LCM, the main technique applied is the Base equalization technique to equalize the denominators to their LCM value first. The common denominator will be the LCM of the three denominators, 3, 9 and 6 which is 18.

Note: For details you may refer to my detailed articles on the topic of base equalization in indices, fractions, and versatile use of the powerful technique.

Transforming the given fractions to this equal denominator value, we get,

$\displaystyle\frac{12}{18}$, $\displaystyle\frac{8}{18}$ and $\displaystyle\frac{15}{18}$.

Now let us repeat the problem: we need to find the LCM of these fractions.

As the denominators are now equal, finding the LCM of the numerators, 12, 8, 15 will give us the solution.

The LCM of 12, 8, 15 is,

$3\times{4}\times{2}\times{5}=120$.

So the required LCM is, $\displaystyle\frac{120}{18}=\displaystyle\frac{20}{3}$.

Answer: d: $\displaystyle\frac{20}{3}$

Problem 2.

Find the largest possible 4 digit number divisible by 45, 18 and 35.

1. 9540
2. 9450
3. 9460
4. 9350

Solution:

Let us find the LCM of the three given numbers. The target number will be a multiple of this LCM.

The LCM of 45, 18 and 35 is,

$=3\times{3}\times{5}\times{2}\times{7}=630$.

Here we employ the method of writing down the factors of the first number in product form, and then the new factors of the second number and so on.

So the target 4 digit number will be a multiple of 630. As largest such 4 digit multiple is required, let us divide the smallest 5 digit number, 10000 with 630 to find the remainder. On dividing we get the remainder as, 550. By subtracting 550 from 10000, that is, 9450 will then be our target largest 4 digit number that is divisible by each of 45, 18 and 35.

The other way is to multiply 630 with the quotient 15 (of division of 10000), to get the same result.

Answer: b: 9450.

Problem 3.

Three bells chime at intervals of 48, 60 and 90 minutes. If all three chime together at 7 am in the morning of 11th May, when will the bells chime together next time?

1. 7 am 12th May
2. 7 pm 11the may
3. 5 pm 11th May
4. 5 am 12th May

Solution:

The bells will chime together at time intervals equal to the LCM of their individual chime periods. Thus LCM of 48, 60 and 90 minutes is,

$=6\times{2}\times{2}\times{2}\times{5}\times{3} = 720$ minutes = 12 hours.

So the next time the bells will chime together will be 7 pm on May 11th itself.

Answer: b: 7 pm 11th May.

Problem 4.

What is the largest number that will divide 99, 123 and 183 leaving same remainder for each?

1. 12
2. 18
3. 6
4. 15

Solution:

If the remainder were given we could have just subtracted the remainder from the three numbers and got the answer as the HCF of the subtraction results. But here the only information given is that the remainder after dividing the three numbers by the HCF is same in all three cases.

To solve this problem we need to use the basic factor concept of difference of two numbers continues to contain the HCF,

If two integers have same factor, the difference of the integers will also have the number as its factor.

We will call use of this special concept as Factor in difference technique. Giving a name to its use will make its use easier and more frequent.

This is as basic a concept as it is important. Let us see how it happens.

Let us assume two numbers with a common factor to be, $y_1 = hx_1$ and $y_2 = hx_2$, where $h$ is the common factor.

The difference of the numbers is then,

$D = y_1 - y_2 = hx_1 - hx_2 = h(x_1 - x_2)$.

Thus the difference $D$ will also have the common factor $h$ as its factor.

In our case, if we subtract, say, 99 from 123 getting 24, we can say, this difference 24 has the desired highest common factor.

Not only have we used the Factor in difference technique here but also we have noted while deducing the difference, that the remainder canceled out, leaving the difference of only the two target numbers.

The same way we get the difference of 183 and 123 as 60 and can now say, the desired HCF is the HCF of 24 and 60, the differences between two pairs of numbers.

Thus, the required largest desired number is HCF of 24 and 60, that is, 12.

Answer: a: 12.

We will leave you now with a set of 10 carefully chosen exercise problems, though to take control you need to solve lots of problems following intelligent methods.

---

Exercise problems

Exercise Problem 1.

Find the largest possible number that may divide each of two numbers sum of which is 1394, when none of the component numbers is zero or equal to each other.

1. 17
2. 34
3. 41
4. 82

Exercise problem 2.

Find the least possible 5 digit number dividing which by each of 12, 10, 16 and 18 leaves a remainder of 5.

1. 10105
2. 10055
3. 10085
4. 10155

Exercise problem 3.

A room is 26 feet long and 10 feet wide. If its floor is to be covered by square tiles, how many minimum number of tiles will be required?

1. 50
2. 60
3. 65
4. 55

Exercise problem 4.

Five bells ring at intervals of 3, 5, 6, 8 and 9 seconds. If all the bells ring once, after how long a period the bells would ring together again?

1. 12 minutes
2. 6 minutes
3. 18 minutes
4. 24 minutes

Exercise problem 5.

The smallest number which when divided by 12, 15, 20 or 54 leaves a remainder of 4 in each case, is

1. 454
2. 564
3. 544
4. 464

Exercise problem 6.

The HCF of two numbers is 4 and LCM is 520. If one of the numbers is 52, the other number is then,

1. 40
2. 42
3. 52
4. 50

Exercise problem 7.

Three sets of books on Maths, Science and Social studies have 240, 336 and 96 books in each set respectively. The books need to be stacked in such a way that all the books are stacked subject-wise and number of books in each stack is same. The total minimum number of stacks will then be,

1. 14
2. 48
3. 22
4. 21

Exercise problem 8.

HCF of the fractions, $\displaystyle\frac{2}{3}$, $\displaystyle\frac{4}{5}$, and $\displaystyle\frac{6}{7}$ is,

1. $\displaystyle\frac{48}{105}$
2. $\displaystyle\frac{2}{105}$
3. $\displaystyle\frac{24}{105}$
4. $\displaystyle\frac{1}{105}$

Exercise problem 9.

A milkman has 21 liters of whole milk, 42 liters of toned milk and 63 liters of double toned milk. If he wants to pack the three types of milk in cans so that in no can two types of milk are mixed, then what is the minimum number of can would he require?

1. 12
2. 9
3. 6
4. 3

Exercise problem 10.

The maximum number of students among whom 910 pens and 1001 pencils can be distributed in such a way that each student gets same number of pens and pencils, is

1. 1911
2. 910
3. 1001
4. 91

---

Answers to Exercise problems

Excercise problem 1. Answer: d: 82.

Exercise problem 2. Answer: c: 10085.

Exercise problem 3. Answer: c: 65.

Exercise problem 4. Answer: b: 6 minutes.

Exercise problem 5. Answer: c: 544.

Exercise problem 6. Answer: a: 40.

Exercise problem 7. Answer: a: 14.

Exercise problem 8. Answer: b: $\displaystyle\frac{2}{105}$.

Exercise problem 9. Answer: c: 6.

Exercise problem 10. Answer: d: 91.

---

Guided help on Number system, HCF LCM in Suresolv

To get the best results out of the extensive range of articles of tutorials, questions and solutions on Number system and HCF LCM in Suresolv, follow the guide,

Suresolv Number system, HCF LCM Reading and Practice Guide for SSC CHSL, SSC CGL, SSC CGL Tier II, Bank PO and Other Competitive exams.

The guide list of articles is up-to-date.

---