Question

Using Euclid's algorithm, find the largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2, and 3 respectively.

Answer 1

On subtracting 1, 2, and 3 from 1251, 9377 and 15628 respectively, we get 1250, 9375 and 15625.


Now we find the HCF of 1250 and 9375 using Euclid's division lemma

1250 < 9375
Thus, we divide 9375 by 1250 by using Euclid's division lemma

9375 = 1250 × 7 + 625

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

1250 = 625 × 2 + 0

Since, Remainder is zero,

Therefore, HCF of 1250 and 9375 is 625.

Now, we find the HCF of 15625 and 625 using Euclid's division lemma.

15625 > 625
Thus, we divide 15625 by 625 by using Euclid's division lemma

15625 = 625 × 25 + 0

Since, Remainder is zero,

Therefore, HCF of 15625 and 625 is 625.

Hence, the largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2, and 3 respectively is 625.