Find H.C.F of 867 and 225 by Euclid's division algorithm.

According to Euclid’s Division Lemma, if a and b are any two positive integers then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

So, apply the lemma on 867 and 225.

We get,

867 = (225 × 3) + 192

Since the remainder is not zero.

Apply the lemma again on 225 and 192.

We get,

225 = (192 × 1) + 33

Since the remainder is not zero.

Apply the lemma again on 192 and 33.

We get,

192 = (33 × 5) + 27

Since the remainder is not zero.

Apply the lemma again on 33 and 27.

We get,

33 = (27 × 1) + 6

Since the remainder is not zero.

Apply the lemma again on 27 and 6.

We get,

27 = (6 × 4) + 3

Since the remainder is not zero.

Apply the lemma again on 6 and 3.

We get,

6 = (3 × 2) + 0

We have finally got remainder as 0.

⇒ HCF (867, 225) = 3