Question

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

Answer 1

We have to find the H.C.F. of $(1251-1=1250),(9377-2=9375),(15628-3=15625),$

Find H.C.F of $1250$ and $9375$ :-

$9375=1250\times 7+625$
$1250=625\times 2+0$

Since, remainder is $0$, the H.C.F is $625$
Now, H.C.F of $(625,15625)$ is
$15625=625\times 25+0$

Hence $625$ is the H.C.F of all the three numbers and divides $1251,9377$ and $15628$ leaving remainders $1,2$ and $3$, respectively.