Using Euclid’s division algorithm, find the HCF of

8840 and 23120

Given numbers are 8840 and 23120

Here, 23120 > 8840

So, we divide 23120 by 8840

By using Euclid’s division lemma, we get

23120 = 8840 × 2 + 5440

Here, r = 5440 ≠ 0.

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

8840 = 5440 × 1 + 3400

Here, r = 3400 ≠ 0

On taking 5440 as dividend and 3400 as the divisor and again we apply Euclid’s division lemma, we get

5440 = 3400 × 1 + 2040

Here, r = 2040 ≠ 0.

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

3400 = 2040 × 1 + 1360

Here, r = 1360 ≠ 0

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

2040 = 1360 × 1 + 680

Here, r = 680 ≠ 0

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

1360 = 680 × 2 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 680, the HCF of 8840 and 23120 is 680.