Use Euclid\'s algorithm to find the HCF of 4052 and 12576.

1.	Use Euclid\'s algorithm to find the HCF of 4052 and 12576.
Answer» According to Euclid’s Division Lemma if we have two positive integers a and b, then there exist unique integers q and r which satisfies the condition a = bq + r where 0 ≤ r ≤ b.HCF is the largest number which exactly divides two or more positive integers.Since 12576 > 405212576 = (4052 × 3) + 420420 is a reminder which is not equal to zero (420 ≠ 0).4052 = (420 × 9) + 272271 is a reminder which is not equal to zero (272 ≠ 0).Now consider the new divisor 272 and the new remainder 148.272 = (148 × 1) + 124Now consider the new divisor 148 and the new remainder 124.148 = (124 × 1) + 24Now consider the new divisor 124 and the new remainder 24.124 = (24 × 5) + 4Now consider the new divisor 24 and the new remainder 4.24 = (4 × 6) + 0Reminder = 0Divisor = 4HCF of 12576 and 4052 = 4. 12576=4052×3+420 4052=420×9+272 420=272×1+148 272=148×1+124 148=124×1+24 124=24×5+4 24=4×6+0 HCF of 12576 and 4052 is 4. 12576=4052×3+4204052=420×9+272420=272×1+148272=148×1+124148=124×1+24124=24×5+424=4×6+0HCF of 12576 and 4052 is 4.

Discussion