Question

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

Answer 1

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 Dividend=Divisor\times 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 + r
$3125=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.