Question

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

​

Answer 1

QUESTION :-

=> Use Euclid's division algorithm to find the HCF of 4052 and 12576.

SOLUTION :-

=> 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.