This post is also available in: हिन्दी (Hindi)

H.C.F. (Highest Common Factor), and L.C.M.(Lowest Common Multiple) are two of the two common concepts in math. The H.C.F. defines the greatest factor present in between given two or more numbers, whereas L.C.M. defines the least number which is exactly divisible by two or more numbers.

In this article, you will understand when to use HCF and LCM in word problems and also understand how to do HCF and LCM problems.

## What is H.C.F.?

H.C.F. or Highest Common Factor is the greatest number that divides each of the two or more numbers. H.C.F. is also called the Greatest Common Measure (G.C.M.) and Greatest Common Divisor(G.CD.).

For example, H.C.F. of 12 and 18 is 6, since 6 is the greatest number that divides both 12 and 18.

Similarly, H.C.F. of 9, 12, and 21 is 3, as 3 is the greatest number that divides all the three numbers 9, 12, and 21.

### Methods of Finding H.C.F.

The most common methods of finding H.C.F. are

- Factorization Method
- Prime Factorization Method
- Division Method
- Shortcut Method

#### Finding H.C.F. – Factorization Method

To find the H.C.F. of two or more numbers using the factorization method following steps are used:

**Step 1:** Write down all the factors of all the numbers.

**Step 2:** Take out the common factors.

**Step 3:** Select the highest number among the numbers found in step 2.

For example, find the H.C.F. of 36 and 45.

Factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, and 36

Factors of 45 are 1, 3, 5, 9, 15 and 45

Common factors are 1, 3, and 9

The highest common factor is 9.

#### Finding H.C.F. – Prime Factorization Method

To find the H.C.F. of two or more numbers using the prime factorization method following steps are used:

**Step 1:** Write down the prime factors of all the numbers.

**Step 2:** Select the common prime factors of the numbers.

**Step 3:** Multiply the common prime factors obtained in step 2.

For example, find the H.C.F. of 36 and 45.

Prime factors of 36 are 2 × 2 × 3 × 3

Prime factors of 45 are 3 × 3 × 5

Common prime factors are 3 and 3.

The highest common factor is 3 × 3 = 9.

#### Finding H.C.F. – Division Method

To find the H.C.F. of two or more numbers using the division method following steps are used:

**Step 1**: Write the given numbers horizontally, in a sequence, by separating them with commas.

**Step 2:** Find the smallest prime number which can divide the given number. It should exactly divide the given numbers. (Write on the left side).

**Step 3:** Now write the quotients.

**Step 4:** Repeat the process, until you reach the stage, where there is no coprime number left.

**Step 5:** We will get the common prime factors as the factors on the left-hand side divides all the numbers exactly. The product of these common prime factors is the HCF of the given numbers.

For example, find the H.C.F. of 36 and 45.

3 | 36 | 45 |

3 | 12 | 15 |

4 | 5 |

The highest common factor is 3 × 3 = 9.

#### Finding H.C.F. – Short Cut Method

To find the H.C.F. of two or more numbers using the shortcut method following steps are used:

**Step 1:** Select any two numbers.

**Step 2:** Make the smaller number a divisor and the greater number a dividend.

**Step 3:** Divide the two numbers in step 2 and find the remainder.

**Step 4:** If the remainder is zero, then the smaller number (divisor) is the H.C.F. else go to step 5.

**Step 5:** Make the divisor as dividend and the remainder as the divisor and go to step 3.

For example, find the H.C.F. of 36 and 45.

The smaller number is 36 and the greater number is 45, so the divisor is 36 and the dividend is 45.

On dividing 45 by 36, the quotient is 1 and the remainder is 9. (45 = 36 × 1 + 9).

The remainder is not equal to 0, so make 36 as the dividend and 9 as the divisor and repeat the process.

The quotient is 4 and the remainder is 0. (36 = 9 × 4 + 0).

Since the remainder is 0, therefore, the highest common factor is 9.

## What is L.C.M.?

L.C.M. (Lowest Common Multiple) of any given numbers is the value that is evenly divisible by the given numbers. It is also called the Least Common Divisor (LCD).

For example, L.C.M. is 14 and 21 is 42.

Similarly, LCM of 6, 15, and 18 is 90.

### Methods of Finding L.C.M.

The most common methods of finding L.C.M. are

- Multiples Method
- Prime Factorization Method

#### Finding L.C.M. – Multiples Method

To find the L.C.M. of two or more numbers using the multiples method following steps are used

**Step 1:** Write down the first few multiples of all the numbers.

**Step 2:** Take out the common multiples.

**Step 3:** Select the lowest number among the numbers found in step 3.

For example, find the L.C.M. of 15 and 18

Multiples of 15 are 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, ….

Multiples of 18 are 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, …

Common multiples are 90, 180, …

Lowest Common Multiple is 90.

#### Finding L.C.M. – Prime Factorization Method

To find the L.C.M. of two or more numbers using the prime factorization method following steps are used

**Step 1:** Express all the numbers as the product of their prime factors.

**Step 2:** Select the prime factors with the highest powers.

**Step 3:** Multiply the numbers obtained in step 3.

For example, find the L.C.M. of 72 and 108

72 = 2 × 2 × 2 × 3 × 3 = 2^3 × 3^2

108 = 2 × 2 × 3 × 3 × 3 = 2^2 × 3^3

Prime factors are 2 and 3 and the highest power with 2 is 3 and that with 3 is 3.

So, L.C.M. is 2^3 × 3^3 = 8 × 27 = 216

## When to Use HCF and LCM in Word Problems?

Let’s now understand how to know when to use HCF or LCM.

Whenever some values are given and the value that you have to calculate is bigger than these numbers, then it is a question of LCM. Similarly, when the value to be calculated is smaller than the given values, then it is a question of HCF.

We find H.C.F. when

- to split things into smaller sections
- to arrange something into rows or groups
- to distribute more numbers of items to large groups
- to figure out how many people we have to invite

Similarly, we find L.C.M. when

- the question talks about the smallest or minimum
- the word ‘together’ or ‘simultaneous’ is used in the question

### Examples

Let’s take some examples to understand the difference.

**Example 1:** Find the least number which when divided by 6, 15, and 18 leave the remainder of 5 in each case.

In this case, we need to find a number that needs to be divided by 6, 15, and 18. So, it must be bigger than 6, 15 and 18. Hence, find L.C.M.

**Example 2:** Two tankers contain 850 liters and 680 liters of kerosene oil respectively. Find the maximum capacity of a container that can measure the kerosene oil of both the tankers when used an exact number of times.

Here, we need to find the capacity of a container that divides the capacity of two given containers equally, so the smaller number and hence find HCF.

**Example 3:** In a morning walk, three friends step off together. Their steps measure 80 cm, 85 cm, and 90 cm respectively. What is the minimum distance each should walk so that all can cover the same distance in complete steps?

In this case, we need to find the distance covered and since the distance covered will be greater than the measure of steps (80 cm, 85 cm, and 90 cm), so find L.C.M.

**Example 4:** Renu purchases two bags of fertilizer of weights 75 kg and 69 kg. Find the maximum value of weight which can measure the weight of the fertilizer an exact number of times.

Here, we are required to find a weight (or a container) that can measure each of the weights (75 kg and 69 kg) equally, so a smaller number and hence, find the H.C.F.

## Let’s Code With Python

Find H.C.F. of given numbers.

# Python program to find H.C.F of two numbers # To take input from the user x = int(input("Enter the first number: ")) y = int(input("Enter the second number: ")) # choose the smaller number if x > y: smaller = y else: smaller = x # check for hcf for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i print("The H.C.F. is ", hcf)

Find L.C.M. of given numbers.

# Python Program to find the L.C.M. of two input number # To take input from the user x = int(input("Enter the first number: ")) y = int(input("Enter the second number: ")) # choose the greater number if x > y: greater = x else: greater = y while(True): if((greater % x == 0) and (greater % y == 0)): lcm = greater break greater += 1 print("The L.C.M. is ", lcm)

## Practice Problems

- Six bells commence tolling together and toll at intervals of 2, 4, 6, 8 10, and 12 seconds respectively. In 30 minutes, how many times do they toll together? (excluding the one at the start)
- The traffic lights at three different road crossings change after every 48 sec, 72 sec, and 108 sec respectively. If they all change simultaneously at 8:20:00 hrs, when will they again change simultaneously?
- A merchant has 120 ltr of and 180 ltr of two kinds of oil. He wants the sell oil by filling the two kinds of oil in tins of equal volumes. What is the greatest of such a tin?
- Find the least number of soldiers in a regiment such that they stand in rows of 15, 20, 25 and form a perfect square.
- Find the least number of square tiles by which the floor of a room of dimensions 16.58 m and 8.32 m can be covered completely.
- A juice seller had three types of juices. 403 liters of 1st kind, 434 liters of 2nd kind, and 465 liters of 3rd kind. Find the least possible number of containers of equal size in which different types of juice can be filled without mixing.
- Lalit is preparing dinner plates. He has 12 pieces of chicken and 16 rolls. If he wants to make all the plates identical without any food left over, what is the greatest number of plates Lalit can prepare?
- The drama club meets in the school auditorium every 2 days, and the choir meets there every 5 days. If the groups are both meeting in the auditorium today, then how many days from now will they next have to share the auditorium?
- Jagdish is printing orange and green forms. He notices that 3 orange forms fit on a page, and 5 green forms fit on a page. If Jagdish wants to print the exact same number of orange and green forms, what is the minimum number of each form that he could print?
- Lalita has collected 8 U.S. stamps and 12 international stamps. She wants to display them in identical groups of U.S. and international stamps, with no stamps left over. What is the greatest number of groups Lalita can display them in?
- Abhay has two pieces of wire, one 6 feet long and the other 12 feet long. If he wants to cut them up to produce many pieces of wire that are all of the same lengths, with no wire left over, what is the greatest length, in feet, that he can make them?

## FAQs

### How do you find an HCF?

The highest common factor (HCF) is found by finding all common factors of two numbers and selecting the largest one. For example, 12 and 18 have common factors of 1, 2, 3, and 6. The highest common factor is 6.

### How do you find an LCM?

LCM denotes the least common factor or multiple of any two or more given integers. For example, L.C.M of 16 and 20 will be 2 x 2 x 2 x 2 x 5 = 80, where 80 is the smallest common multiple for numbers 16 and 20.

### Where should we use LCM and HCF?

When we have to find a number larger than given numbers, then we find LCM. If we have to find smaller number, then we find HCF

## Conclusion

H.C.F. and L.C.M. both are important concepts in math. It is important to know the situation when one should use H.C.F. and when to use L.C.M.