Question

Find the H.C.F. of 867 and 255 using Euclid's division algorithm.

Hint:

Euclid's division algorithm is a method to find the H.C.F. by repeatedly dividing the larger number by the smaller number and replacing the larger number with the smaller number and the smaller number with the remainder until the remainder becomes zero.

Answer 1

To find the H.C.F. of 867 and 255, we use Euclid's division algorithm. The algorithm is based on the principle that the H.C.F. of two numbers is the same as the H.C.F. of the smaller number and the remainder when the larger number is divided by the smaller number. Step 1: Apply Euclid's algorithm. Divide 867 by 255: \[ 867 \div 255 = 3 \quad \text{(quotient)} \quad \text{and} \quad 867 - 3 \times 255 = 102 \quad \text{(remainder)}. \] Thus, \[ 867 = 3 \times 255 + 102. \] Step 2: Apply Euclid's algorithm again to 255 and 102. Divide 255 by 102: \[ 255 \div 102 = 2 \quad \text{(quotient)} \quad \text{and} \quad 255 - 2 \times 102 = 51 \quad \text{(remainder)}. \] Thus, \[ 255 = 2 \times 102 + 51. \] Step 3: Apply Euclid's algorithm again to 102 and 51. Divide 102 by 51: \[ 102 \div 51 = 2 \quad \text{(quotient)} \quad \text{and} \quad 102 - 2 \times 51 = 0 \quad \text{(remainder)}. \] Thus, \[ 102 = 2 \times 51 + 0. \] Step 4: Conclusion. Since the remainder is now 0, the divisor at this step, 51, is the H.C.F. of 867 and 255.
Conclusion:
The H.C.F. of 867 and 255 is 51.