Question 29

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

Solution:

To find the largest number that divides 1251, 9377, and 15628 leaving remainders 1, 2, and 3 respectively, we can follow these steps:

1. Subtract the Remainders:
– For 1251, subtract 1:
$$1251-1=1250$$
– For 9377, subtract 2:
$$9377-2=9375$$
– For 15628, subtract 3:
$$15628-3=15625$$

2. Find the HCF of the New Numbers:
We need to find the highest common factor (HCF) of 1250, 9375, and 15625. We can use the Euclidean algorithm for this.

3. Calculate HCF of 1250 and 9375:
– Apply the Euclidean algorithm:
$$9375=1250\times 7+125$$
– Next, apply the algorithm again:
$$1250=125\times 10+0$$
– Since the remainder is 0, the HCF of 1250 and 9375 is 125.

4. Calculate HCF of 125 and 15625:
– Now apply the Euclidean algorithm:
$$15625=125\times 125+0$$
– Again, since the remainder is 0, the HCF of 125 and 15625 is 125.

5. Conclusion:
The largest number that divides 1251, 9377, and 15628 leaving remainders 1, 2, and 3 respectively is 125.