Use Euclid’s Division Algorithm to find the HCF of 867 and 255

Introduction

In this problem, we will find the Highest Common Factor (HCF) of the numbers 867 and 255. Let us understand the solution step by step using Euclid’s Division Algorithm, just like a teacher explains in class.

Video Solution

Question

Use Euclid’s Division Algorithm to find the HCF of 867 and 255.

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 867 by 255.

867 = 255 × 3 + 102

Step 2: Now divide 255 by 102.

255 = 102 × 2 + 51

Step 3: Now divide 102 by 51.

102 = 51 × 2 + 0

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

Therefore, the HCF of 867 and 255 is 51.

Conclusion

Hence, using Euclid’s Division Algorithm, we find that the Highest Common Factor (HCF) of 867 and 255 is 51.

Hence proved.