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.

☛ Check: NCERT Solutions for Class 10 Maths Chapter 1

---

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

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.

---

☛ Related Questions:

• Show that any positive odd integer is of the form 6q +1, or 6q + 3, or 6q + 5, where q is some integer.
• An army contingent of 616 members is to march behind an army band of 32 members in a parade. The two groups are to march in the same number of columns. What is the maximum number of columns in which they can march?
• Use Euclid’s division lemma to show that the square of any positive integer is either of form 3m or 3m + 1 for some integer m.[Hint: Let x be any positive integer then it is of the form 3q, 3q + 1 or 3q + 2. Now square each of these and show that they can be rewritten in form of 3m or 3m + 1.]
• Use Euclid’s division lemma to show that the cube of any positive integer is of the form 9m, 9m + 1, or 9m + 8.