# Concept: LCM & HCF

CONTENTS

**INTRODUCTION**

A **Factor** of a given number completely divides it. **Example**: Factors of 6 are 1, 2, 3 and 6.

i.e., 6 is completely divisible by 1 or 2 or 3 or 6.

A **Multiple** of a given number is such that the number completely divides the multiple. **Example**: Multiples of 6 are 6, 12, 18 and 24.

i.e., 6 completely divides 6 or 12 or 18 or 24.

- A given Natural number will always have finite factors.
- A given Natural number will always have infinite multiples.
- A given Natural number is always a factor as well as a multiple of itself.

**EUCLID'S DIVISION LEMMA**

If a number 'N' is divided by 'd' giving quotient 'q' and remainder 'r', then we can form an equation:

N = d × q + r

Here,

N = Dividend

d = divisor

q = quotient

r = remainder

**LOWEST COMMON MULTIPLE (LCM)**

The **Lowest Common Multiple (LCM)** of 2 or more numbers is the lowest number which is divisible by all the given numbers.

**Example**: Let us take two numbers 4 and 6.

Multiples of 4 are 4, 8, 12, 16, 20 and so on

Multiples of 6 are 6, 12, 18, 24 and so on

We can see that the lowest common multiple is 12, i.e., 12 is the lowest number which is completely divisible by both 4 and 6.

We can calculate LCM of any given numbers by prime factorising then and taking the highest power available of all distinct prime numbers.

**Example**: Find LCM of 10, 12 and 15.

**Solution:**

Let us prime factorise 10, 12 and 15.

10 = 2 × 5

12 = 2^{2} × 5

15 = 3 × 5

The distinct prime factors for given numbers are 2, 3 and 5

Highest power of these prime numbers i.e., 2, 3 and 5 in the given numbers is 2, 1 and 1.

∴ LCM(10, 12 and 15) = 2^{2} × 3^{1} × 5^{1} = 60

**Example**: Find LCM of 36, 48 and 64.

**Solution:**

Let us prime factorise 36, 48 and 64.

36 = 2^{2} × 3^{2}

48 = 2^{4} × 3

64 = 2^{6}

The distinct prime factors for given numbers are 2 and 3

Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 6 and 2.

∴ LCM(36, 48 and 64) = 2^{6} × 3^{2} = 576

**LCM APPLICATION TYPE 1**

A number which when divided by a, b or c leaves the same remainder r = LCM(a, b, c) × k + r

**Example**: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1.

**Solution:**

Let smallest such number is N.

N when divided by 2 leaves remainder of 1.

∴ N = 2 × a + 1

⇒ N - 1 = 2 × a ...(1)

N when divided by 3 leaves remainder of 1.

∴ N = 3 × b + 1

⇒ N - 1 = 3 × b ...(2)

N when divided by 5 leaves remainder of 1.

∴ N = 5 × c + 1

⇒ N - 1 = 5 × c ...(3)

From (1), (2) and (3) we can say that N - 1 is a multiple of 2, 3 and 5.

∴ N - 1 will be a multiple of LCM(2, 3, 5)
⇒ N - 1 = LCM(2, 3, 5) × k

⇒N = LCM(2, 3, 5) × k + 1
⇒ N = 30k + 1

For N to be smallest 2-digit number we put k = 1, hence N = 31.

**LCM APPLICATION TYPE 2**

The greatest number which when divided by a, b or c leaves remainders p, q and r respectively such that (a - p) = (b - q) = (c - r) = d (say)

then, N = LCM(a, b, c) × k - d

**Example**: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1, 2 and 4 respectively.

**Solution:**

Let smallest such number is N.

Here, divisors are 2, 3 and 5 while remainders are 1, 2 and 4 respectively such that

2 - 1 = 3 - 2 = 5 - 4 = 1 (d)

N when divided by 2 leaves remainder of 1.

∴ N = 2 × a + 1

⇒ N - 1 = 2 × a

Adding 2 (divisor) both sides we get

N + 1 = 2(a + 1) ...(1)

N when divided by 3 leaves remainder of 2.

∴ N = 3 × b + 2

⇒ N - 2 = 3 × b

Adding 3 (divisor) both sides we get

N + 1 = 3(b + 1) ...(2)

N when divided by 5 leaves remainder of 4.

∴ N = 5 × c + 4

⇒ N - 4 = 5 × c

Adding 5 (divisor) both sides we get

N + 1 = 5(c + 1) ...(3)

From (1), (2) and (3) we can say that N + 1 is a multiple of 2, 3 and 5.

∴ N + 1 will be a multiple of LCM(2, 3, 5)
⇒ N + 1 = LCM(2, 3, 5) × k

⇒ N = LCM(2, 3, 5) × k - 1 (d)
⇒ N = 30k - 1

For N to be smallest 2-digit number we put k = 1, hence N = 29.

**LCM APPLICATION TYPE 3**

The greatest number which when divided by a or b leaves remainder p and q respectively such that (a - p) ≠ (b - q)

then, N = LCM(a, b) × k + n

where, n is the smallest such number which needs to found out by a little hit and trial method.

**Example**: Find the highest 2-digit number which when divided by 3 or 5 leaves remainder of 1 and 4 respectively.

**Solution:**

Let smallest such number is n.

Here, divisors are 2 and 5 while remainders are 1 and 4 respectively such that

3 - 1 ≠ 5 - 4

n when divided by 5 leaves remainder of 4.

∴ n = 5 × a + 4

⇒ n can be 4, 9, 14, 19, 24, 29, ... etc.

Now smallest value of n which when divided by 3 gives remainder 1 is 4.

Now we can generalise, any number which when divided by 3 or 5 and gives remainders as 1 or 4 respectively (N) = LCM(3, 5) × k + 4 = 15k + 4

For N to be highest 2-digit number (N) = 15k + 4 < 100

15k < 96

k < 6.4

Highest possible value of k = 6

Highest 2-digit value of N = 15 × 6 + 4 = 94

**Example**: Find the smallest 3-digit number which when divided by 12 or 15 leaves remainder of 2 and 8 respectively.

**Solution:**

Let smallest such number is n.

Here, divisors are 12 and 15 while remainders are 2 and 8 respectively such that

12 - 2 ≠ 15 - 8

n when divided by 15 leaves remainder of 8.

∴ n = 15 × a + 8

⇒ n can be 8, 23, 38, 53, 68, 83, ... etc.

Now smallest value of n which when divided by 12 gives remainder 2 is 38.

Now we can generalise, any number which when divided by 12 or 15 and gives remainders as 2 or 8 respectively (N) = LCM(12, 15) × k + 38 = 60k + 38

For N to be smallest 3-digit number (N) = 60k + 38 > 99

⇒ 60k > 61

⇒ k > 1.01

Least possible value of k = 2

Smallest 3-digit value of N = 60 × 2 + 38 = 158

**HIGHEST COMMON HCF (HCF)**

The **Highest Common Factor (HCF)** or Greatest Common Divison (GCD) of 2 or more numbers is the highest number which can divide all the given numbers.

**Example**: Let us take two numbers 4 and 6.

Factors of 4 are 1, 2 and 4

Factors of 6 are 1, 2, 3 and 6

We can see that the highest common factor is 2, i.e., 2 is the highest number which can completely divide both 4 and 6.

We can calculate HCF of any given numbers by prime factorising then and taking the smallest power available of only common distinct prime numbers.

**Example**: Find HCF of 12 and 18.

**Solution:**

Let us prime factorise 12 and 18.

12 = 2^{2} × 3

18 = 2 × 3^{2}

The common distinct prime factors for given numbers are 2 and 3

Smallest power of these prime numbers i.e., 2 and 3 in the given numbers is 1 and 1.

∴ HCF(12 and 18) = 2 × 3 = 6

**Example**: Find HCF of 36, 48 and 60.

**Solution:**

Let us prime factorise 36, 48 and 64.

36 = 2^{2} × 3^{2}

48 = 2^{4} × 3

60 = 2^{2} × 3 × 5

The common distinct prime factors for given numbers are 2 and 3

Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 2 and 1.

∴ LCM(36, 48 and 60) = 2^{2} × 3 = 12

**HCF APPLICATION TYPE 1**

The greatest number which divides X, Y and Z leaving remainders p, q and r = HCF[(X - p), (Y - q), (Z - r)]

**Example**: The greatest number which divides 53 and 68 leaving remainders 5 and 8

**Solution:**

Let the required number be p.

53 when divided by p leaves a remainder of 5

∴ 53 = p × a + 5

⇒ 53 - 5 = p × a
⇒ a = (53 - 5)/p ...(1)

68 when divided by p leaves a remainder of 8

∴ 68 = p × b + 8

⇒ 68 - 8 = p × b

b = (68 - 8)/p ...(2)

From (1) and (2)

Since, a and b are integers, p should completely divided (53 - 5) and (68 - 8) i.e., 48 and 60

Highest possible value of p = HCF(48 and 60) = 12.

**Example**: The greatest number which divides 327, 223 and 411 leaving remainders 15, 7 and 3

**Solution:**

Highest possible such number = HCF[(327 - 15), (223 - 7), (411 - 3)] = HCF[312, 216, 408].

312 = 2^{3} × 3 × 13

216 = 2^{3} × 3^{3}

408 = 2^{3} × 3 × 17

∴HCF[312, 216, 408] = 2^{3} × 3 = 24

**HCF APPLICATION TYPE 2**

The greatest number which divides X, Y and Z leaving the same remainder = HCF[(X - Y), (Y - Z), (Z - X)]

**Example**: The greatest number which divides 470, 545 and 410 leaving remainders 5 and 8

**Solution:**

Let the required number be p.

470 when divided by p leaves a remainder of say r

∴ 470 = p × a + r

⇒ 470 - r = p × a ...(1)

545 when divided by p leaves a remainder of say r

∴ 545 = p × b + r

⇒ 545 - r = p × b ...(2)

410 when divided by p leaves a remainder of say r

∴ 410 = p × c + r

⇒ 410 - r = p × c ...(3)

(1) - (3)

470 - 410 = p(a - c)

a - c = (470 - 410)/p ...(4)

(2) - (3)

545 - 410 = p(b - c)

b - c = (545 - 410)/p ...(5)

(2) - (1)

545 - 470 = p(b - a)

b - a = (545 - 470)/p ...(6)

From (4), (5) and (6)

Highest possible value of p = HCF[(470 - 410), (545 - 410), (545 - 470)] = 15

**Example**: The greatest number which divides 559, 415 and 343 leaving remainders 5 and 8

**Solution:**

Let the required number be p.

Highest possible value of p = HCF[(559 - 415), (415 - 343)] = 72

**Note**: Taking LCM of 2 pairs will give the same answer as taking LCM of all 3 pairs.

- For any number of numbers, LCM is always a multiple of HCF.

**LCM & HCF OF TWO NUMBERS**

Let the LCM of two number 'a' and 'b' be 'L' while their HCF be 'H'.

Now 'a' = as H × x and 'b' = H × y

Since H is the highest common factor between 'a' and 'b', hence x and y will have not common factor i.e., x and y will be co-prime numbers.

Also, LCM of numbers consist of all the factors possible, hence L = H × x × y

∴ L × H = a × b

i.e., Product of two numbers is equal to product of their LCM and HCF

**Note**: The above relation is true only for two numbers and should not be extended to more than 2 numbers.

**Example**: Let us take two numbers 24 and 60.

HCF (24, 60) = 12

LCM (24, 60) = 120

Now, 12 × 120 = 1440 while 24 × 60 = 1440

**Example**: How many pair of numbers exist such that their HCF is 12 and LCM is 72.

**Solution:**

Let the required numbers be a and b.

Since their HCF is 12, a = 12x and b = 12y where x and y are co-prime numbers.

Now, product of two numbers = product of their HCF and LCM

∴ a × b = LCM × HCF

⇒ 12x × 12y = 12 × 72
⇒ x × y = 6

Now, we need to write 6 as a product of two co-prime numbers.

⇒ 6 = 1 × 6 or 2 × 3

∴ x = 12 and y = 72 or x= 24 and y = 36

⇒ 2 pair of values are possible.