Using Euclid’s division algorithm, find the HCF of

135 and 225

Given numbers are 135 and 225

Here, 225 > 135

So, we divide 225 by 135

By using Euclid’s division lemma, we get

225 = 135 × 1 + 90

Here, r = 90 ≠ 0.

On taking 135 as dividend and 90 as the divisor and we apply Euclid’s division lemma, we get

135 = 90 × 1 + 45

Here, r = 45 ≠ 0

So, on taking 90 as dividend and 45 as the divisor and again we apply Euclid’s division lemma, we get

90 = 45 × 2 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 45, the HCF of 135 and 225 is 45.