# Use Euclid's division algorithm to find the HCF of: 1. 135 and 225, 2. 196 and 38220, 3. 867 and 225

Solutions for 'Use Euclid's division algorithm to find the HCF of: i. 135 and 225, ii. 196 and 38220, iii. 867 and 225'

**Solutions for 'Use Euclid's division algorithm to find the HCF of: i. 135 and 225, ii. 196 and 38220, iii. 867 and 225' **

**i. 135 and 225**

As we can see from the question 225 is greater than 135. Therefore, by Euclid’s division algorithm, we have,

**225 = 135 × 1 + 90**

Now, remainder 90 ≠ 0, thus again using division lemma for 90, we get,

**135 = 90 × 1 + 45**

Again, 45 ≠ 0, repeating the above step for 45, we get,

**90 = 45 × 2 + 0**

The remainder is now zero, so our method stops here. Since, in the last step, the divisor is 45, therefore, HCF (225,135) = HCF (135, 90) = HCF (90, 45) = 45.

Hence, the HCF of 225 and 135 is 45.

**ii. 196 and 38220**

In this given question, 38220>196, therefore the by applying Euclid’s division algorithm and taking 38220 as the divisor, we get,

**38220 = 196 × 195 + 0**

We have already got the remainder as 0 here. Therefore, HCF(196, 38220) = 196.

**Hence, the HCF of 196 and 38220 is 196.**

**iii. 867 and 225**

As we know, 867 is greater than 225. Let us apply now Euclid’s division algorithm on 867, to get,

**867 = 225 × 3 + 102**

Remainder 102 ≠ 0, therefore taking 225 as the divisor and applying the division lemma method, we get,

**225 = 102 × 2 + 51**

Again, 51 ≠ 0. Now 102 is the new divisor, so repeating the same step we get,

**102 = 51 × 2 + 0**

The remainder is now zero, so our procedure stops here. Since, in the last step, the divisor is 51, therefore, HCF (867,225) = HCF(225,102) = HCF(102,51) = 51.

**Hence, the HCF of 867 and 225 is 51.**