Question

Find the HCF of 124,286 by Euclid's Division Lemma

Answer 1

Answer:

2

Step-by-step explanation:

Set up a division problem where a is larger than b.

a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.

286 ÷ 124 = 2 R 38    (286 = 2 × 124 + 38)

124 ÷ 38 = 3 R 10    (124 = 3 × 38 + 10)

38 ÷ 10 = 3 R 8    (38 = 3 × 10 + 8)

10 ÷ 8 = 1 R 2    (10 = 1 × 8 + 2)

8 ÷ 2 = 4 R 0    (8 = 4 × 2 + 0)

When remainder R = 0, the HCF is the divisor, b, in the last equation. HCF = 2

Answer 2

Answer:

Euclid's division lemma :

Let a and b be any two positive Integers .

Then there exist two unique whole numbers q and r such that

a = bq + r ,

0 ≤ r <b

Now ,

Clearly, 286 > 124

Start with a larger integer , that is 286.

Applying the Euclid's division lemma to 286 and 184, we get

286 = 2 × 124 + 38

Since the remainder 38 ≠ 0, we apply the Euclid's division lemma to divisor 124 and remainder 38 to get

124 = 3 × 38 + 10

We consider the new divisor 38 and remainder 10 and apply the division lemma to get

38 = 3 × 10 + 8

We consider the new divisor 10 and remainder 8 and apply the division lemma to get

10 = 1 × 8 + 2

We consider the new divisor 8 and remainder 2 and apply the division lemma to get

8 = 4 × 2 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 4 is the HCF of 286 and 124.