Question

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 are divisible by the required number.

Now, required number = HCF(1250, 9375, 15625)

By Euclid’s division algorithm,

a = bq + r  .......(i)  [∵ Dividend = Divisor × Quotient + Remainder]

Let a = 15625 and b = 9375

15625 = 9375 × 1 + 6250 .......[From equation (i)]

`\implies` 9375 = 6250 × 1 + 3125

`\implies` 6250 = 3125 × 2 + 0

∴ HCF(15625, 9375) = 3125

Now, we take c = 1250 and d = 3125

Then again using Euclid’s division algorithm, d = cq + r

`\implies` 3125 = 1250 × 2 + 625

`\implies` 1250 = 625 × 2 + 0

∴ HCF(1250, 9375, 15625) = 625

Hence, 625 is the largest number which divides 1251, 9377 and 15628 leaving remainders 1, 2 and 3, respectively.