# Find the largest number which on dividing 1251, 9377 and 15628 leave remainders 1, 2 and 3 respectively. - Mathematics

Sum

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.

Concept: Euclid’s Division Lemma
Is there an error in this question or solution?

Share