Using Euclid’s division algorithm, find the HCF of

3318 and 4661

Given numbers are 3318 and 4661

Here, 4661 > 3318

So, we divide 4661 by 3318

By using Euclid’s division lemma, we get

4661 = 3318 × 1 + 1343

Here, r = 1343 ≠ 0.

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

3318 = 1343 × 2 + 632

Here, r = 632 ≠ 0

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

1343 = 632 × 2 + 79

Here, r = 79 ≠ 0

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

632 = 79 × 8 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 79, the HCF of 3318 and 4661 is 79.