Use Euclid’s division algorithm to find the HCF of: 867 and 255

To find the Highest Common Factor (HCF) of 867 and 255 using Euclid’s division algorithm, we follow a systematic approach involving division and remainders.

Step 1: Initial Division

First, divide the larger number by the smaller number:

• 867 ÷ 255 = 3 (quotient)
• Remainder = 867 - (255 × 3) = 102

Step 2: Repeat the Process

Now, take the previous divisor (255) and divide it by the remainder (102):

• 255 ÷ 102 = 2 (quotient)
• Remainder = 255 - (102 × 2) = 51

Step 3: Continue Dividing

Next, divide the last divisor (102) by the new remainder (51):

• 102 ÷ 51 = 2 (quotient)
• Remainder = 102 - (51 × 2) = 0

Final Result

Since the remainder is now 0, the last non-zero remainder is the HCF. Therefore, the HCF of 867 and 255 is:

51