 # Using Euclid’s division algorithm, `
Question:

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

Solution:

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=b q+r$  $\ldots($ i)

$[\because$ dividend $=$ divisor $\times$ quotient $+$ remainder $]$

For largest number, put $a=15625$ and $b=9375$

$15625=9375 \times 1+6250 \quad$ [ from Eq. (i)]

$\Rightarrow \quad 9375=6250 \times 1+3125$

$\Rightarrow \quad 6250=3125 \times 2+0$

$\therefore \quad \operatorname{HCF}(15625,9375)=3125$

Now, we take $c=1250$ and $d=3125$, then again using Euclid's division algorithm,

$d=c q+r \quad$ [from Eq. (i)]

$\Rightarrow \quad 3125=1250 \times 2+625$

$\Rightarrow \quad 1250=625 \times 2+0$

$\therefore \quad \operatorname{HCF}(1250,9375,15625)=625$

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