Find the largest number which on dividing 1251, 9377 and 15628 leave remainders 1, 2 and 3 respectively.
Solution
It is given that 1, 2 and 3 are the remainders of 1251, 9377 and 15628, respectively.
Subtracting these remainders from the respective numbers, we get
1251 − 1 = 1250
9377 − 2 = 9375
15628 − 3 = 15625
Now, 1250, 9375 and 15625 are divisible by the required number.
Required number = HCF of 1250, 9375 and 15625
By Euclid's division algorithm a = bq + r, 0 ≤ r < b
For largest number, put a = 15625 and b = 9375
15625 = 9375 × 1 + 6250
⇒ 9375 = 6250 × 1 +6250
⇒ 6250 = 3125 × 2 + 0
Since remainder is zero, therefore, HCF(15625 and 9375) = 3125
Further, take c = 1250 and d = 3125. Again using Euclid's division algorithm
d = cq + r, 0 ≤ r < c
⇒ 3125 = 1250 × 2 +625 ...[∵ r ≠ 0]
⇒ 1250 = 625 × 2 + 0
Since remainder is zero, therefore, HCF(1250, 9375 and 15625) = 625
Hence, 625 is the largest number which divides 1251, 9377 and 15628 leaving remainder 1, 2 and 3, respectively.
