Find the HCF (Highest Common Factor) of the following pairs of number by Euclid Division Algorithm:

867, 255

From the integers given in the question 867 and 255, it is observed that 867 > 255. So by Euclid’s Division Lemma we get the following:

867 = 255 × 3 + 102

Here the remainder is 102 which is not equal to zero. So applying Euclid’s Division Lemma on divisor 255 and remainder 102.

255 = 102 × 2 + 51

Here the remainder is 51 which is not equal to zero. So applying Euclid’s Division Lemma on divisor 102 and remainder 51.

102 = 51 × 2 + 0

So from the above relation is seen that remainder zero is obtained.

So the HCF of 867 and 255 is 51.

The entire process can be expressed in the following way: