Using Euclid's algorithm, find the largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2, and 3 respectively.
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.