Q.

The largest number that divides 1251, 9377 and 15628 leaving remainder 1, 2 and 3, respectively by using Euclid’s division algorithm is ____.


see full answer

Start JEE / NEET / Foundation preparation at rupees 99/day !!

21% of IItians & 23% of AIIMS delhi doctors are from Sri Chaitanya institute !!
An Intiative by Sri Chaitanya

(Unlock A.I Detailed Solution for FREE)

Ready to Test Your Skills?

Check your Performance Today with our Free Mock Test used by Toppers!

Take Free Test

Detailed Solution

Since 1, 2, and 3 are the remainders of 1251, 9377, and 15628.
Since we were told to leave the remainder, subtracting this remainder from the appropriate numbers gives us,
 ⇒1251−1=1250
 ⇒9377−2=9375
⇒15628−3=15625.
Now we need to find H.C.F.( 1250, 9375, 15625) which is the largest number required.
Euclid's division algorithm is a=bq+r, 0 ⩽ r < b.
Step 1: For the largest number, enter a=15625a=15625 and b=9375b=9375
⇒15625=9375×1+6250
(When we divide 15625 by 9375, we get a remainder of 6250.)
Now we take 9375 as dividend and 6250 as divisor,
 ⇒9375=6250×1+3125
(When 9375 is divided by 6250, we get 3125 as a remainder.)
Now we take 6250 as dividend and 3125 as divisor,
 ⇒6250=3125×2+0
We stop here because if we take 0 as a divisor, the solution is undefined.
So 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 enter a=3125 and b=1250
Follow the same procedure as in step 1:
 ⇒3125=1250×2+625
⇒1250=625×2+0
The remainder is zero, so we end here.
H.C.F (15625, 9375, 1250) = 625.
625 is the largest number that divides 1251, 9377, and 15628, so the remainder is 1, 2, and 3.
So the correct answer is "625".
 
Watch 3-min video & get full concept clarity
score_test_img

Get Expert Academic Guidance – Connect with a Counselor Today!

whats app icon
The largest number that divides 1251, 9377 and 15628 leaving remainder 1, 2 and 3, respectively by using Euclid’s division algorithm is ____.