Question

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

Answer 1

find the largest number that divides 1251,9377,and 15628 leaving remainders 1,2 & 3

1251 leaves remainder 1
=> 1251-1 = 1250

9377 leaves remainder 2
=> 9377-2 = 9375

15628 leaves remainder 3
=> 15628-3 = 15625

The largest number that divides 1251,9377,and 15628 leaving remainders 1,2 & 3 will be the HCF of 1250,9375 and 15625

====================
Finding HCF using Euclid division lemma:-

a = bq + r

0 ≤ r < b

a > b

First,find the HCF of 15625 and 9375

15625 = 9375 × 1 + 6250

⟹ 9375 = 6250 × 1 + 3125

⟹ 6250 = 3125 × 2 + 0

remainder(r) = 0

∴ HCF (15625 and 9375) = 3125

Now,find the HCF of 3125 and 1250

3125 = 1250 × 2 + 625

1250 = 625 × 2 + 0

remainder(r) = 0

∴ HCF (3125 and 1250) = 625

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

Hope it helps