 # Real Numbers | HCF Euclid's Division Algorithm

Exercise 1.1 Q1 CBSE Class 10 Maths NCERT Solution

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

i. 135 and 225
ii. 196 and 38220
iii. 867 and 255

##### 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