##### NCERT Solutions for Class 10 Maths | Chapter: Real Numbers | Concept: Euclid's Division Algorithm

#### Question 1: Use Euclid’s division algorithm to find the HCF of:

i. 135 and 225

ii. 196 and 38220

iii. 867 and 255

#### Explanatory Answer

##### i. 135 and 225

Because 225 > 135 let us apply Euclid’s division lemma with 225 as dividend and 135 as divisor

**Step 1:** 225 = 135 × 1 + 90

The remainder in this step is not zero. So, proceed to step 2.

**Step 2:** Apply the lemma to 135 and 90.

135 = 90 × 1 + 45

The remainder in this step is not zero. So, proceed to step 3.

**Step 3:** Apply the lemma to 90 and 45.

90 = 45 × 2 + 0

The remainder has become zero in the 3rd step. ∴ the divisor of this step is the HCF.

The HCF is 45

##### ii. 196 and 38220

38220 > 196. So, 38220 will be the dividend and 196 will be the divisor.

**Step 1:** Apply Euclid’s division lemma to 38220 and 196

38220 = 196 × 195 + 0

The remainder has become zero in the 1st step.

∴ 196 divides 38220 and 196 is the HCF of 38220 and 196

##### iii. 867 and 255

867 > 255. So, 867 will be the dividend and 255 will be the divisor.

**Step 1:** Apply Euclid’s division lemma to 867 and 255

867 = 255 × 3 + 102

The remainder in this step is not zero. So, proceed to step 2.

**Step 2:** Apply Euclid’s division lemma to 255 and 102

255 = 102 × 2 + 51

The remainder in this step is not zero. So, proceed to step 3.

**Step 3:** Apply Euclid’s division lemma to 102 and 51

102 = 51 × 2 + 0

The remainder has become zero in the 3rd step

∴ The divisor of this step is the HCF

The HCF of 867 and 225 is 51