Using Euclid’s Division Algorithm Find the Largest Number That Divides 1251, 9377 and 15628 Leaving Remainders 1, 2 and 3

Video Explanation

Watch the video below to understand the complete solution step by step:

Solution

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

Step 1: Subtract the Given Remainders

If a number leaves remainder 1 when dividing 1251, then it exactly divides:

1251 − 1 = 1250

If a number leaves remainder 2 when dividing 9377, then it exactly divides:

9377 − 2 = 9375

If a number leaves remainder 3 when dividing 15628, then it exactly divides:

15628 − 3 = 15625

Step 2: Find the HCF of 1250, 9375 and 15625

Using Euclid’s division algorithm:

9375 = 1250 × 7 + 625

1250 = 625 × 2 + 0

So, HCF (1250, 9375) = 625

Now find HCF of 625 and 15625:

15625 = 625 × 25 + 0

Since the remainder is zero,

∴ HCF (1250, 9375, 15625) = 625

Final Answer

∴ The largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2 and 3 respectively is 625.

Conclusion

Thus, by subtracting the given remainders and applying Euclid’s division algorithm, we find that the required largest number is 625.