Question

use Euclid's division algorithm to find HCF of
426 and 576

Answer 1

576=426*1+150
426=150*2+126
150=126*1+24
126=24*5+6
24=6*4+0
therefore 6 is the hcf

Answer 2

Given: Two numbers-  426 and 576

To find: HCF of given numbers using Euclid's Division Lemma

Solution:

(Definition - According to Euclid's division lemma, if we have two positive integers a and b, then there exist unique integers q an r which satisfies the condition a = bq + r where 0 ≤ r < b)

The greater integer is 576 and smaller is 426

We need to apply Euclid's Division Lemma (a = bq + r) on the given numbers, where a = 576 and b = 426.

We get,

⇒ 576 = 426 × 1 + 150

Now, we need to apply Euclid's Division Lemma again taking a = 426 and b = 150

⇒ 426 = 150 × 2 + 126

Taking a = 150 and b = 126

⇒ 150 = 126 × 1 + 24

Taking a = 126 and b = 24

⇒ 126 = 24 × 5 + 6

Taking a = 24 and b = 6

⇒ 24 = 6 × 4 + 0

As the remainder has become 0, we can't proceed further.

Now, the divisor is 6 when remainder is 0.

Hence, 6 is the HCF of 426 and 576.