Question

Using Euclid’s division algorithm, find the HCF of 4052 and 12576.

Answer 1

Given numbers are 4052 and 12576

Here, 12576 > 4052

So, we divide 12576 by 4052

By using Euclid’s division lemma, we get

12576 = 4052 × 3 + 420

Here, r = 420 ≠ 0.

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

4052 = 420 × 9 + 272

Here, r = 272 ≠ 0

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

420 = 272 × 1 + 148

Here, r = 148 ≠ 0

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

272 = 148 × 1 + 124

Here, r = 124 ≠ 0.

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

148 = 124 × 1 + 24

Here, r = 24 ≠ 0

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

124 = 24 × 5 + 4

Here, r = 4 ≠ 0

So, on taking 24 as dividend and 4 as the divisor and again we apply

Euclid’s division lemma, we get

24 = 4 × 6 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 4, the HCF of 4052 and 12576 is 4.