Use Euclid’s Division Algorithm to find the HCF of 135 and 225

Introduction

In this problem, we will find the Highest Common Factor (HCF) of the numbers 135 and 225. Let us solve it step by step using Euclid’s Division Algorithm, the method commonly taught in class.

Video Solution

Question

Use Euclid’s Division Algorithm to find the HCF of 135 and 225.

Solution

According to Euclid’s Division Algorithm, we divide the larger number by the smaller number and then divide the divisor by the remainder. We repeat this process until the remainder becomes zero.

Step 1: Divide 225 by 135.

225 = 135 × 1 + 90

Step 2: Now divide 135 by 90.

135 = 90 × 1 + 45

Step 3: Now divide 90 by 45.

90 = 45 × 2 + 0

Since the remainder has become zero, the divisor at this step is the HCF.

Therefore, the HCF of 135 and 225 is 45.

Conclusion

Hence, using Euclid’s Division Algorithm, we find that the Highest Common Factor (HCF) of 135 and 225 is 45.

Hence proved.