# Use Euclid's division algorithm to find the HCF of:

(i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255

**Solution:**

We will be finding the HCF of given integers by using Euclid’s Division Lemma. It is a technique to compute the highest common factor of two given positive integers.

To obtain the HCF of two positive integers say a and b with a > b, follow the steps described below:

Step I: Apply Euclid’s division lemma to a and b. So, we find whole numbers q and r such that: a = bq + r, 0 ≤ r < b

NOTE: Here, a = dividend, b = divisor, q = quotient, r = remainder.

Step II: If r = 0, b is the HCF of a and b. If r ≠ 0, apply Euclid's division lemma to b and r.

Step III: Continue the process until the remainder is zero. The divisor at this stage will be the required HCF.

(i) 135 and 225

In this case, 225 > 135. We apply Euclid’s division lemma to 135 and 225 and get 225 = (135 × 1) + 90

Since, the remainder r ≠ 0, we apply the division lemma to 135 and 90 to get 135 = (90 × 1) + 45

Since, the remainder r ≠ 0, now, we consider 90 as the divisor and 45 as the remainder and apply division lemma, to get 90 = (45 × 2) + 0

Since the remainder is zero and the divisor is 45, therefore, the HCF of 135 and 225 is 45.

(ii) 196 and 38220

38220 is greater than 196. We apply Euclid’s division lemma to 38220 and 196, to get 38220 = (196 × 195) + 0

Since the remainder is zero and the divisor in this step is 195, therefore, the HCF of 38220 and 196 is 196.

(iii) 867 and 255

867 is greater than 225 and on applying Euclid’s division lemma to 867and 225, we get 867 = (255 × 3) + 102

Since the remainder r ≠ 0, we apply the division lemma to 225 and 102 to get 255 = (102 × 2) + 51

Again, the remainder is not zero, we apply Euclid’s division lemma to 102 and 51 which gives us 102 = (51 × 2) + 0

Since the remainder is zero and the divisor is 51, therefore, the HCF of 867 and 255 is 51.

**Video Solution:**

## Use Euclid's division algorithm to find the HCF of: (i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255

### NCERT Solutions Class 10 Maths Chapter 1 Exercise 1.1 Question 1 - Chapter 1 Exercise 1.1 Question 1:

**Summary:**

The HCF of 135 and 225, 196 and 38220, and 867 and 255 using Euclid's division algorithm are 45, 196, and 51 respectively.