# 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

**a**from divisor**b**then we get**q**as a quotient &**r**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...*