Question

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

Answer 1

Hint: We know that Euclid's division algorithm is \[a = bq + r\] , \[0 \leqslant r < b\] . Where \[r\] is Remainder, \[q\] is Quotient \[b\] is Divisor and \[a\] is dividend. They asked us to find the largest number that divides the given 3 numbers, meaning we need to find H.C.F. of three numbers. Leaving a remainder means we need to subtract the original number with remainder.

Complete step-by-step answer:
Given that 1, 2 and 3 are the remainders of 1251, 9377 and 15628 respectively.
Since they told us to leave the remainder, subtracting these remainder from respective numbers we get,
 \[ \Rightarrow 1251 - 1 = 1250\]
 \[ \Rightarrow 9377 - 2 = 9375\]
 \[ \Rightarrow 15628 - 3 = 15625\] .
Now we need to find the H.C.F.( 1250, 9375, 15625), which is the required largest number.
Euclid's division algorithm is \[a = bq + r\] , \[0 \leqslant r < b\] .
Step 1: For largest number, put \[a = 15625\] and \[b = 9375\]
 \[ \Rightarrow 15625 = 9375 \times 1 + 6250\]
(When we divide 15625 by 9375 we get the remainder 6250.)
Now taking 9375 as dividend and 6250 as divisor,
 \[ \Rightarrow 9375 = 6250 \times 1 + 3125\]
 (When 9375 is divided by 6250 we get 3125 as a remainder.)
Now taking 6250 as dividend and 3125 as divisor,
 \[ \Rightarrow 6250 = 3125 \times 2 + 0\]
We stop here because if we take 0 as a divisor the solution is undefined.
Thus H.C.F (15625, 9375) is 3125.
Now H.C.F (3125, 1250) is equal to H.C.F (15625, 9375, 1250).
Step 2: We need to find H.C.F (3125, 1250)
Now, put \[a = 3125\] and \[b = 1250\]
Following the same procedure as we did in Step 1:
 \[ \Rightarrow 3125 = 1250 \times 2 + 625\]
 \[ \Rightarrow 1250 = 625 \times 2 + 0\]
Remainder is zero, hence we stop here.
H.C.F (15625, 9375, 1250) = 625.
$625$ is the largest number that divides 1251, 9377 and 15628 leaving remainder 1, 2 and 3, respectively.
So, the correct answer is “625”.

Note: In Euclidean algorithm we stop when the remainder is zero and take the divisor as the H.C.F. of the respective numbers. Similarly we can find H.C.F. of any numbers easily. Take the largest number first and then the smallest number. Remember the calculation method we did in the first step. We use the same procedure in all the problems including Euclidean algorithm division.