# LCM and HCF

Suppose there are two numbers, a and b. If a number a divides another number b exactly, then a is **factor** of b and b is called **multiple** of a.

### Highest Common Factor (HCF)

A **common factor** of two or more numbers is a number which divides each of them exactly. For example, 4 is a common factor of 8 and 12.

Highest common factor (HCF) of two or more non-zero integers, is the largest positive integer that divides the numbers exactly. For example, 6 is the highest common factor of 12, 18 and 24. Highest common factor is also called Greatest Common Divisor (GCD).

There are two methods of finding the HCF of a given set of numbers:

**1. Prime Factors Method**

- Step 1: Express each one of the given numbers as the product of prime factors.
- Step 2: Choose common factors.
- Step 3: Find the product of these common factors. This is the required HCF of given numbers.

**Example:** Find the HCF of 360 and 132

360 = 2^{3} × 3^{2} × 5

132 = 2^{2} × 3^{1} × 11

HCF = 2^{2} × 3^{1} = 12

**2. Division Method (for two numbers)**

Divide the larger number by the smaller one. Now, divide the divisor by the remainder. This is continued until no remainder is left. The last divisor is the required HCF.

**3. To find HCF of more than two numbers**

H.C.F. of [(H.C.F. of any two) and (the third number)] gives the HCF of three given numbers.

### Least Common Multiple (LCM)

A **common multiple** of two or more numbers is a number which is exactly divisible by each one of them. For example, 32 is a common multiple of 8 and 16.

Least Common Multiple (LCM) of two or more given numbers is the smallest positive number which is exactly divisible by each of them. For example, consider two numbers 12 and 18.

Multiples of 12 are 12, 24, 36, 48, 72, ...

Multiples of 18 are 18, 36, 54, 72, ...

Common multiples are 36, 72, ...

Least common multiple of 12 and 18 is 36.

**1. Prime Factors Method**

- Step 1: Resolve each given number into prime factors.
- Step 2: Take out all factors with highest powers that occur in given numbers.
- Step 3: Find the product of these factors. This product will be the L.C.M.

**Example:** Find the LCM of 32, 48, 60 and 320

32 = 2^{5}

48 = 2^{4} × 3

60 = 2^{2} × 3 × 5

320 = 2^{6} × 5

LCM = 2^{6} × 3 × 5 = 960

**2. Division Method**

- Step 1: The given numbers are written in a line separated by common.
- Step 2: Divide by any one of the prime numbers 2, 3, 5, 7, 11, ... which will divide at least any two of the given numbers exactly. The quotients and the undivided numbers are written in a line below the first.
- Step 3: Step 2 is repeated until a line of numbers (prime to each other) appears.
- Step 4: Find the product of all divisors and numbers in the last line which is the required LCM.

### Product of Two Numbers

Product of two numbers = Product of their HCF and LCM

a x b = HCF x LCM

### HCF and LCM of Decimals

- Step 1: Make the same number of decimal places in all the given numbers by suffixing zeros if necessary.
- Step 2: Find the HCF or LCM of these numbers without decimal.
- Step 3: Put the decimal point leaving as many digits on its right as there are in each of the numbers.

### HCF and LCM of Fractions

If the given set of numbers includes fractions as well as whole numbers, treat whole number too as fraction with 1 in its denominator. The HCF of a number of fractions is always a fraction, but the LCM may be a fraction or an integer.

HCF = (HCF of Numerators) / (LCM of Denominator)

LCM = (LCM of Numerators) / (HCF of Denominator)

### Applications of HCF and LCM

**1. Find the greatest number that will exactly divide x, y and z.**

Required number = HCF of x, y, and z (greatest divisor).

**Example:** Find the greatest number that will exactly divide 200 and 320

The required greatest number = HCF of 200 and 320 = 40

**2. Find the greatest number that will divide x, y and z leaving remainders a, b and c respectively.**

Required number (greatest divisor) = HCF of (x - a), (y - b) and (z - c).

**Example:** Find the greatest number that will divide 148, 246 and 623 leaving remainders 4, 6 and 11, respectively

The required greatest number = HCF of (148 - 4), (246 - 6) and (623 - 11)

HCF of 144, 240 and 612 = 12

**3. Find the Least Number which is exactly divisible by x, y and z.**

Required number = LCM of x, y and z (least divided).

**Example:** What is the smallest number which is exactly divisible by 36, 45, 63 and 80?

The required smallest number = LCM of 36, 45, 63 and 80 = 5040

**4. Find the least number which when divided by x, y and z leaves the remainders a, b and c respectively.**

Then, it is always observed that (x - a) = (y - b) = (z - c) = k (say).

Required number = (L.C.M. of x, y and z) - k

**Example:** Find the least number which when divided by 9, 10 and 15 leaves the remainders 4, 5 and 10, respectively.

Here. 9 - 4 = 10 - 5 = 15 - 10 = 5

Also, LCM (9, 10, 15) = 90

The required least number = 90 - 5 = 85

**5. Find the least number which when divided by x, y and z leaves the same remainder r in each case.**

Required number = (LCM of x, y and z) + r.

**Example:** Find the least number which when divided by 12, 16 and 18, will leave in each case a remainder 5

The required smallest number = (LCM of 12, 16 and 18) + 5

= 144 + 5 = 149

**6. Find the greatest number that will divide x, y and z leaving the same remainder in each case.**

When the value of remainder is not given, required number = HCF of |(x - y)|, |(y - z)| and |(z - x)|

When the value of remainder r is given, required number = HCF of (x - r), (y - r) and (z - r).

**Example:** Find the greatest number which will divide 772 and 2778 so as to leave the remainder 5 in each case

The required greatest number = HCF of (772 - 5) and (2778 - 5)

= HCF of 767 and 2773

= 59

**Example:** Find the greatest number which on dividing 152, 277 and 427 leaves equal remainder.

The required greatest number = HCF of |(x - y)|, |(y - z)| and |(z - x)|

= HCF of |(152 - 277)|, |(277 - 427)| and |(427 - 152)|

= HCF of 125, 275 and 150

= 25

**7. Find the n-digit greatest number which, when divided by x, y and z leaves no remainder or leaves remainder K in each case.**

- Step 1: LCM of x, y and z = L
- Step 2: Find remainder (R) when n-digit greatest number is divided by L
- Step 3: Required number = (n-digit greatest number - R) + K

**Example:** Find the greatest number of 4 digits which, when divided by 12, 18, 21 and 28, leaves 3 as a remainder in each case.

LCM of 12, 18, 21 and 28 = 252

Remainder when 9999 is divided by 252 = 171

The required number = (9999 - 171) + 3 = 9931

**8. Find the n-digit smallest number which when divided by x, y and z leaves no remainder or leaves remainder K in each case.**

- Step 1: LCM of x, y and z = L
- Step 2: Find remainder (R) when n-digit smallest number is divided by L
- Step 3: Required number = n-digit smallest number + (L - R) + K

**Example:** Find the smallest 4-digit number, such that when divided by 12, 18, 21 and 28, it leaves remainder 3 in each case

LCM of 12, 18, 21 and 28 = 252

Remainder when 1000 is divided by 252 = 244

The required number = 1000 + (252 - 244) + 3 = 1011

### Examples

**Example 1: **What is the greatest number which exactly divides 110, 154 and 242?

The required number is the HCF of 110, 154 and 242.

110 = 2 × 5 × 11

154 = 2 × 7 × 11

242 = 2 × 11 × 11

∴ HCF = 2 × 11 = 22

**Example 2:** What is the greatest number, which when divides 3 consecutive odd numbers produces a remainder of 1.

If x, y, z be 3 consecutive odd numbers, then the required number will be the HCF of x - 1, y - 1 and z - 1.

Since x-1, y-1 and z-1 are 3 consecutive even integers, their HCF will be 2.

So, the answer is 2.

**Example 3:** What is the highest 3 digit number, which is exactly divisible by 3, 5, 6 and 7?

The least number which is exactly divisible by 3, 5, 6, and 7 is LCM (3, 5, 6, 7) = 210.

So, all the multiples of 210 will be exactly divisible by 3, 5, 6 and 7.

So, such greatest 3 digit number is 840 (210 × 4).

**Example 4:** In a farewell party, some students are giving pose for photograph, If the students stand at 4 students per row, 2 students will be left if they stand 5 per row, 3 will be left and if they stand 6 per row 4 will be left. If the total number of students are greater than 100 and less than 150, how many students are there?

If ‘N’ is the number of students, it is clear from the question that if N is divided by 4, 5, and 6, it produces a remainders of 2, 3, & 4 respectively.

Since (4 - 2) = (5 - 3) = (6 - 4) = 2, the least possible value of N is LCM (4, 5, 6) - 2 = 60 - 2 = 58.

But, 100 < N < 150.

So, the next possible value is 58 + 60 = 118

**Example 5: **There are some students in the class. Mr.X brought 130 chocolates and distributed to the students equally, then he was left with some chocolates. Mr Y brought 170 chocolates and distributed equally to the students. He was also left with the same no of chocolates as Mr X was left. Mr Z brought 250 chocolates, did the same thing and left with the same no of chocolates. What is the max possible no of students that were in the class?

The question can be stated as, what is the highest number, which divides 130, 170 and 250 gives the same remainder.

HCF of (170 -130), (250 -170), (250 -130)

HCF (40, 80, 120) = 40