Using Euclid’s division algorithm, find the HCF of 250, 175 and 425.

1.	Using Euclid’s division algorithm, find the HCF of 250, 175 and 425.
Answer» Given numbers are 250, 175 and 425 ∴ 425 > 250 > 175 On applying Euclid’s division lemma for 425 and 250, we get 425 = 250 × 1 + 175 Here, r = 175 ≠ 0. So, again applying Euclid’s division lemma with new dividend 250 and new divisor 175, we get 250 = 175 × 1 + 75 Here, r = 75 ≠ 0 So, on taking 175 as dividend and 75 as the divisor and again we apply Euclid’s division lemma, we get 175 = 75 × 2 + 25 Here, r = 25 ≠ 0. So, again applying Euclid’s division lemma with new dividend 75 and new divisor 25, we get 75 = 25 × 3 + 0 Here, r = 0 and divisor is 25. So, HCF of 425 and 225 is 25. Now, applying Euclid’s division lemma for 175 and 25, we get 175 = 25 × 7 + 0 Here, remainder = 0 So, HCF of 250, 175 and 425 is 25.

Answer»

Given numbers are 250, 175 and 425

∴ 425 > 250 > 175

On applying Euclid’s division lemma for 425 and 250, we get

425 = 250 × 1 + 175

Here, r = 175 ≠ 0.

So, again applying Euclid’s division lemma with new dividend 250 and new divisor 175, we get

250 = 175 × 1 + 75

Here, r = 75 ≠ 0

So, on taking 175 as dividend and 75 as the divisor and again we apply Euclid’s division lemma, we get

175 = 75 × 2 + 25

Here, r = 25 ≠ 0.

So, again applying Euclid’s division lemma with new dividend 75 and new divisor 25, we get

75 = 25 × 3 + 0

Here, r = 0 and divisor is 25.

So, HCF of 425 and 225 is 25.

Now, applying Euclid’s division lemma for 175 and 25, we get

175 = 25 × 7 + 0

Here, remainder = 0

So, HCF of 250, 175 and 425 is 25.

Discussion