Question

Using Euclid's division algorithm, find the HCF of
(i) 612 and 1314
(ii) 1260 and 7344
(iii) 4052 and 12576

Answer 1

(i) 612 and 1314

612 < 1314
Thus, we divide 1314 by 612 by using Euclid's division lemma

1314 = 612 × 2 + 90

∵ Remainder is not zero,
∴ we divide 612 by 90 by using Euclid's division lemma

612 = 90 × 6 + 72

∵ Remainder is not zero,
∴ we divide 90 by 72 by using Euclid's division lemma

90 = 72 × 1 + 18

∵ Remainder is not zero,
∴ we divide 72 by 18 by using Euclid's division lemma

72 = 18 × 4 + 0

Since, Remainder is zero,

Hence, HCF of 612 and 1314 is 18.

(ii) 1260 and 7344

1260 < 7344
Thus, we divide 7344 by 1260 by using Euclid's division lemma

7344 = 1260 × 5 + 1044

∵ Remainder is not zero,
∴ we divide 1260 by 1044 by using Euclid's division lemma

1260 = 1044 × 1 + 216

∵ Remainder is not zero,
∴ we divide 1044 by 216 by using Euclid's division lemma

1044 = 216 × 4 + 180

∵ Remainder is not zero,
∴ we divide 216 by 180 by using Euclid's division lemma

216 = 180 × 1 + 36

∵ Remainder is not zero,
∴ we divide 180 by 36 by using Euclid's division lemma

180 = 36 × 5 + 0

Since, Remainder is zero,

Hence, HCF of 1260 and 7344 is 36.

(iii) 4052 and 12576

4052 < 12576
Thus, we divide 12576 by 4052 by using Euclid's division lemma

12576 = 4052 × 3 + 420

∵ Remainder is not zero,
∴ we divide 4052 by 420 by using Euclid's division lemma

4052 = 420 × 9 + 272

∵ Remainder is not zero,
∴ we divide 420 by 272 by using Euclid's division lemma

420 = 272 × 1 + 148

∵ Remainder is not zero,
∴ we divide 272 by 148 by using Euclid's division lemma

272 = 148 × 1 + 124

∵ Remainder is not zero,
∴ we divide 148 by 124 by using Euclid's division lemma

148 = 124 × 1 + 24

∵ Remainder is not zero,
∴ we divide 124 by 24 by using Euclid's division lemma

​124 = 24 × 5 + 4

∵ Remainder is not zero,
∴ we divide 24 by 4 by using Euclid's division lemma

24 = 4 × 6 + 0

Since, Remainder is zero,

Hence, HCF of 4052 and 12576 is 4.