How to find HCF by Euclid's Division Lemma, no need to prime factorisation












Euclid's Division Lemma





Euclid's Division Lemma is a method from which we find the HCF of two number a & b.

When we divide dividend from divisor then we get as a quotient & as a remainder.

Here the general form of Euclid's division lemma-

a = bq + r & where,

a = dividend
b = divisor
q = quotient
r = remainder

0 ≤ r ≤ b (the remainder r is greater or equal to zero & it is smaller or equal to divisor b)

Remember, You wrote these general form in your previous classes as-

Dividend = Divisor × Quotient + Remainder

Different Methods to find H.C.F. (Highest common factor)

1.) Prime Factorisation Method

As the name of this method, we find the Highest Common Method (H.C.F.) from getting prime factors of numbers.

Take common factors from it & then multiply common factors to get H.C.F.

Its benefit is to find H.C.F between more than two numbers at one time.

2.) Euclid's Division Lemma or algorithm

In Euclid's division lemma, we find H.C.F. by dividing dividend from divisor up to remainder became zero.

Demerits of this method are to find H.C.F. for only two numbers at a time.

In this article, we will discuss how to find H.C.F. by Euclid's division lemma.

How to find H.C.F. by Euclid's Division Lemma-

1.) Example:-

Find the H.C.F. of 455 & 42 by Euclid's Division lemma.


Here 455 > 42 

By Euclid's Division Algorithm -

a = bq + r

Dividend = Divisor × Quotient + Remainder

STEP 1

Now 455 is dividend a, 42 is divisor b.

& 0 ≤ r ≤ 42

( If we divide 455 by 42 so we get quotient 10 & remainder 35)

a = bq + r

455 = 42 × 10 + 35 

STEP 2

Now 42 will be dividend a, 35 is divisor b.

& 0 ≤ r ≤ 35

( If we divide 42 by 35 so we get quotient 1 & remainder 7)

a = bq + r

42 = 35 × 1 + 7

STEP 3

Now 35 is dividend a, 7 is divisor b.

& 0 ≤ r ≤ 7

( If we divide 35 by 7 so we get quotient 5 & remainder 0)

a = bq + r

35 = 7 × 5 + 0

Now we get remainder 0 & our divisor is 7 so our H.C.F. is 7.

2.) Example:-

Find the H.C.F. of 420 & 130 by Euclid's Division Lemma.

Solve:-

Here 420 > 130 

By Euclid's Division Algorithm -

a = bq + r

Dividend = Divisor × Quotient + Remainder

STEP 1

Now 420 is dividend a, 130 is divisor b.

& 0 ≤ r ≤ 130

( If we divide 420 by 130 so we get quotient 3 & remainder 30)

a = bq + r

420 = 130 × 3 + 30 

STEP 2

Now 130 will be dividend a, 30 is divisor b.

& 0 ≤ r ≤ 30

( If we divide 130 by 30 so we get quotient 4 & remainder 10)

a = bq + r

130 = 30 × 4 + 10

STEP 3

Now 30 is dividend a, 10 is divisor b.

& 0 ≤ r ≤ 10

( If we divide 30 by 10 so we get quotient 3 & remainder 0)

a = bq + r

30 = 10 × 3 + 0

Now we get remainder 0 & our divisor is 10 so our H.C.F. is 10.




For any query related to the article. So you may contact us & if it is helpful so please share...