# LCM and HCF

HCF (highest common factor): HCF of two or more numbers x1, x2, …… ,xn is the greatest number which will completely divide the numbers x1, x2, …… ,xn.

LCM (least common multiple): LCM of two or more numbers x1, x2, …… ,xn is the least number y such that x1, x2, …… ,xn completely divides the y.

There are two methods of finding LCM and HCF

1. By prime factorisation

Suppose we have to find the HCF and LCM of 12 and 18

12 = $2\times2\times3$ = $2^{2}\times3$

18 = $2\times3\times3$ = $2\times3^{2}$

___________________________________________________

HCF = $2\times3$ = 6

LCM = $2^{2}\times3^{2}$ = 36

In HCF, we take numbers with least power.

In LCM,we take the numbers with highest power.

2. Euclid’s division algorithm : It is used to calculate the HCF ( Highest Common Factor ) of two positive integers.

if  we have to calculate the HCF of two positive integers a and b, with a > b, then apply the following steps

Step 1 : Apply euclid’s lemma to a and b. So there exist unique integers q and r such that a = bq + r ,  Where   0 r < b

Step 2 : if r = 0, then b is the HCF of a and b. If r is not equal to zero, then again apply the euclid’s division lemma to b and r.

Step 3 : continue this process till the remainder is zero.

Step 4 : the divisor at the last stage will be the HCF of a and b

Example: Find the H.C.F. of 55 and 66.

$66 = 55\times1+11$

$55 = 11\times5$ + 0

$\Rightarrow$ HCF = 11

2. Find the HCF of 52 and 299.

$299 = 52\times5+39$

$52 = 39\times1+13$

$39 = 13\times3+0$

$\Rightarrow$ HCF (52, 299) = 13

### L.C.M. and H.C.F. of fractions $\frac{a}{b}$ and $\frac{c}{d}$

LCM ( $\frac{a}{b}$, $\frac{c}{d}$) = $\frac{LCM (a,c)}{HCF(b,d)}$

HCF ( $\frac{a}{b}$, $\frac{c}{d}$) = $\frac{HCF (a,c)}{LCM(b,d)}$

For example: Find the HCF and LCM of $\frac{3}{14}$ and $\frac{9}{21}$

Solution: LCM($\frac{3}{14}$, $\frac{9}{21}$) = $\frac{LCM (3,9)}{HCF(14,21)}$ = $\frac{9}{7}$

HCF($\frac{3}{14}$, $\frac{9}{21}$) = $\frac{HCF (3,9)}{LCM(14,21)}$ =

$\frac{3}{42}$ = $\frac{1}{14}$

## Few questions of HCF and LCM

1. Find the H.C.F. of 1457 and 2491

a) 47

b)53

c) 51

d) 1

Solution: $2491= 1457\times1+1034$

$1457= 1034\times1+423$

$1034= 423\times2+188$

$423= 188\times2+47$

$188= 47\times4+0$

$\Rightarrow$ HCF (1457, 2491) = 47

2. The L.C.M. and H.C.M. of two numbers are 660 and 12 respectively. If one number is 132, find the other.

a) 80

b) 45

c) 60

d) 70

Solution: HCF $\times$ LCM = 132 $\times$ x

660 $\times$ 12 = 132 $\times$ x

x = $\frac{660\times12}{132}$ = 60

3 . what is the greatest number, which when divide 989 and 1327 leave remainders 5 and 7 respectively

a) 8

b) 16

c) 24

d) 32

Solution: Let the number be x which when divide 989 and 1327 leaves remainder 5 and 7 respectively

989 – 5 = 984

1327 – 7 = 1320

It means that x is the greatest number which completely divide the numbers 984 and 1320.

So, x is the H.C.F. of 984 and 1320

984   = $2^{3}\times3\times41$

1320 = $2^{3}\times3\times5\times11$

HCF = $2^{3}\times3\$ = 24

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

a) 450

b) 454

c) 540

d) 544

Solution: Let x is the least number which when divided by 12, 15, 20 or 54 leaves a remainder of 4

It means x – 4 is completely divide by 12, 15, 20 or 54

So, x – 4 is the LCM of 12, 15, 20 or 54.

LCM (12, 15, 20 and 54)

So, x – 4 = 540

x = 544

5. Find the LCM and HCF of $\frac{2}{5}$ and $\frac{4}{15}$

a) $\frac{2}{5}$ and $\frac{4}{15}$

b) $\frac{4}{5}$ and $\frac{2}{15}$

c) $\frac{2}{5}$ and $\frac{2}{15}$

d) $\frac{4}{5}$ and $\frac{4}{15}$

Solution: LCM($\frac{2}{5}$, $\frac{4}{15}$) = $\frac{LCM (2,4)}{HCF(5,15)}$ = $\frac{4}{5}$

HCF($\frac{2}{5}$, $\frac{4}{15}$) = $\frac{HCF (2,4)}{LCM(5,15)}$ =$\frac{2}{15}$

6. If the ratio of two numbers is 3 : 4 and their LCM is 336, then the HCF of two numbers is

a) 7

b) 14

c) 21

d) 28

Solution: Let the numbers be 3x and 4x

Then HCF  = x

$LCM\times HCF$ = $3x\times 4x$

$336\times x$ = $3x\times 4x$

336x  = $3x\times 4x$

x  = $\frac{336}{12}$ = 28

7. The sum of two numbers is 280 and their HCF is 35. How many pairs of such numbers are there ?

a) 1

b) 2

c) 3

d) 0

Solution: Since the HCF (a, b) is 35

$\Rightarrow$ a and b are the multiples of 35

$\Rightarrow$ a = 35x and b = 35y

$\Rightarrow$ 35x + 35y = 280

x + y = $\frac{280}{35}$ = 8

Partition of 8 into two numbers whose HCF is 1

1 and 7

3 and 5

$\Rightarrow$ There are two pairs $35\times1$ = 35 and $35\times7$= 245  (35, 245)

and $35\times3$ = 105  and $35\times5$ = 175             (105, 175)