Question

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

• A. 620
• B. 625
• C. 650
• D. 675

Answer 1

The correct option is B 625

Since, 1, 2 and 3 are the remainders of 1251, 9377 and 15628, respectively. Thus, after subtracting these remainders from the numbers,
We have the numbers, 1251 - 1 = 1250, 9377 - 2 = 9375 and 15628 - 3 = 15625 which is divisible by the required number.
Now, required number = HCF of 1250, 9375 and 15625 [for the largest number]
By Euclid's division algorithm,
$a=bq+r....[\because \text{dividend = divisor}\times \text{quotient + remainder}]$
For largest number, put a = 15625 and b = 9375
$15625=9375\times 1+6250$
$9375=6250\times 1+3125$
$6250=3125\times 2+0$
HCF (15625, 9375) = 3125
Now, we take c = 1250 and d = 3125, then again using Euclid's division algorithm,
$d=cq+r3125=1250\times 2+625$
$1250=625\times 2+0$
HCF (1250, 9375, 15625) = 625
Hence, 625 is the largest number which divides 1251, 9377 and 15628 leaving remainder 1, 2 and 3, respectively.