Sponsor Area

Real Numbers

Question
CBSEENMA10006240

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

Solution

 Given integers are 4052 and 12576, clearly 12576 > 4052.

Therefore, by applying Euclid's division lemma to 4052 and 12576, we get

I. 12576 = 4052 × 3 + 420

II. Since the remainder 420 ≠ 0, we apply division lemma to 4052 and 420 to get

III. We consider the new divisor 420 and new remainder 272 and apply division lemma to gel   

IV. We consider the new divisor 272 and new remainder 148 and apply division lemma to get


V. We consider the new divisor 148 and new remainder 124 and apply division lemma to get

VI. We consider the new divisor 124 and new remainder 24 and apply division lemma to get

VII.We consider the new divisor 24 and new remainder 4 and apply division lemma to get

The remainder at this step is zero. So, the divisor at this stage or the remainder at the previous stage i.e. 4 is the HCF of 4052 and 12576.