Use Euclid's algorithm to find the …

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 > 4052 12576 = (4052 × 3) + 420 420 is a reminder which is not equal to zero (420 ≠ 0). 4052 = (420 × 9) + 272 271 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) + 124 Now consider the new divisor 148 and the new remainder 124. 148 = (124 × 1) + 24 Now consider the new divisor 124 and the new remainder 24. 124 = (24 × 5) + 4 Now consider the new divisor 24 and the new remainder 4. 24 = (4 × 6) + 0 Reminder = 0 Divisor = 4 HCF 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+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.