# 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.

Remember:
• 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 = 22 × 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) = 22 × 31 × 51 = 60

Example: Find LCM of 36, 48 and 64.

Solution:
Let us prime factorise 36, 48 and 64.

36 = 22 × 32
48 = 24 × 3
64 = 26

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) = 26 × 32 = 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 = 22 × 3
18 = 2 × 32

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 = 22 × 32
48 = 24 × 3
60 = 22 × 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) = 22 × 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 = 23 × 3 × 13
216 = 23 × 33
408 = 23 × 3 × 17

∴HCF[312, 216, 408] = 23 × 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.

Remember:
• 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.

## Feedback

Help us build a Free and Comprehensive Preparation portal for various competitive exams by providing us your valuable feedback about Apti4All and how it can be improved.