ICOME
    FOLLOW US: facebook twitter instagram youtube

HCF and LCM

H.C.F

Highest Common Factor(H.C.F) or Greatest Common Factor(G.C.F) or Greatest Common Divisor(G.C.D)

THe largest or greatest among the common divisors of two or more integers is called HCF or GCD of the given integers, for two or more positive integers it always exist and it is unique.
There are two methods to find H.C.F

(i) Prime factorization method (fundamental theorem of arithematic).

In this method,
(a) Find prime factors for all given positive integers.

(b) Select common prime factors having least exponents.
eg . Find H.C.F of 144 and 180
144 = 24 x 32
180 = 22 x 32 x 5
H.C.F = 22 x 32 = 4 x 9 = 36
H.C.F = 36
(ii) Long Division Method (or Euclid lemma)

(a) Apply Euclid's lemma to a and b and obtain whole numbers q(quotient) and r (remainder).
Such that :
a = bq1 + r , 0 <= r < b
If r = 0 , then b is H.C.F of a and b.

(b) If r is not equal to 0 , then again apply Euclid lemma.
b = rq1 + r1
If r1, then r is HCF of a and b .

(c) If r1 is not equal to 0 again apply Euclid lemma r will be divident and r1 will be divisor .

Illustration:
Use H.C.F of 144 and 180
Apply Euclid Division Lemma
180 = 144 x 1 + 36

144 = 36 x 4 + 0
So, H.C.F = 36
Important Points:

(i) Product of two given numbers = product of their H.C.F and L.C.M (Relation between HCF and LCM).

(ii) If two given numbers are co-prime, then their HCF is 1.
Product of the two given numbers = Their L.C.M

(iii) The H.C.F of two numbers always divides their L.C.M exactly (leaving zero remainder)
When to Use H.C.F

(i) The H.C.F of two or more numbers is the greatest number that divides each of them exactly.

(ii) The L.C.M of two or more numbers is the least number that is divisible by all these numbers.

(iii) H.C.F of given fraction =

(iv) L.C.M of given fraction =

(v) Find the largest number which divides a,b,c leaving remainders x,y and z.
In the case the required no. is = H.C.F of (a-x) , (b-y) , (c-z).

(vi) Find the maximum capacity of a container which can measure the liquid in either of the given tank exact number of times.

(vii) The ratio of two numbers is a:b (lowest for,indivisible to each other, or common factor is one), then
Numbers are ak and bk , where k is a constant so,
H.C.F is k and L.C.M is abk

(viii) The largest number which when divide the numbers a,b and c give remainder as p,q,r respectively is given by
H.C.F of (a-b), (b-c) and (c-a)

L.C.M

L.C.M



The L.C.M of two or more numbers is the smallest number into which each of the numbers is the numbers will divide without a remainder.
Consider the numbers 6,12 and 8.
The multiples of 6, 12,18,24,30,36,42,48,54
The multiples of 12 are 12,24,36,60
THe multiples of 8 are 8,16,24,32,40,48,56
The L.C.M is 48.
There are two methods to find L.C.M

(i) Prime factorization :
(a) Find prime factors for all given numbers.

(b) Take product of all prime factors having greatest exponents.

eg . 6 = 2 x 3
12 = 22 x 3
8 = 23
L.C.M = 23 x 3 = 24
(ii) Common Division Method :

In this method, take product of divisors and undivided numbers to get L.C.M
eg .

L.C.M = 23 x 3 = 24
L.C.M of 6,8,and 12 is 24.
When to use L.C.M

(i) Find the least number which when divided by a, b, and c leaves a remainder of x in each case
In this case required no = (L.C.M of a,b,c) + x

(ii) When events occur after a certain time interval, then find the time zone when they meet together .

(iii) Find the smallest number which when divided by a,b,c leaves remainder x,y,z respectively.
In this case required number will be = (LCM of a,b,c) - k
k = a-x = b-y = c-z