Find the HCF of 255 and 867 by Euclid's division algorithm.

Asked by Topperlearning User | 11th Dec, 2013, 10:05: AM

Expert Answer:

Since 867 > 255, apply Euclid's division lemma, to a =867 and b=255 to find q and r such that 867 = 255q+r, 0 r < 255

On dividing 867 by 255 we get quotient as 3 and remainder as 102

i.e 867 = 255 3 + 102

Since remainder 102 0, we apply the division lemma to a=255 and b= 102 to find whole numbers q and r such that 255 = 102q + r where 0 r<102

On dividing 255 by 102 we get quotient as 2 and remainder as 51

i.e 255 = 102 x 2 + 51

Again remainder 51 is non zero, so we apply the division lemma to a=102 and b= 51 to find whole numbers q and r such that 102 = 51 q + r where 0 r<51 

On dividing 102 by 51 quotient is 2 and remainder is 0 i.e 102 = 51 x 2 + 0

Since the remainder is zero, the divisor at this stage is the HCF

Since the divisor at this stage is 51,therefore, HCF of 867 and 255 is 51.

Answered by  | 11th Dec, 2013, 12:05: PM