Question

Use Euclid division algorithm find HCF 4952and 12576in note

Answer 1

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, 12576 > 4052

Applying the Euclid's division lemma to 12576 and 4052, we get

12576 = 4052 x 3 + 420

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

4052 = 420 x 9 + 272

We consider the new divisor 420 and remainder 272 and apply the division lemma to get

420 = 272 x 1 + 148

We consider the new divisor 272 and remainder 148 and apply the division lemma to get

272 = 148 x 1 + 124

We consider the new divisor 148 and remainder 124 and apply the division lemma to get

148 = 124 x 1 + 24

We consider the new divisor 124 and remainder 24 and apply the division lemma to get

124 = 24 x 5 + 4

We consider the new divisor 24 and remainder 4 and apply the division lemma to get

24 = 4 x 6 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 4 is the HCF of 12576 and 4052.

Answer 2

Answer:

to find HCF of 4952 and 12576 using Euclid's division algorithm

4952 < 12576

12576 = 4952 × 2 + 2672

4952 = 2672 × 1 + 2280

2672 = 2280 × 1 + 392

2280 = 392 × 5 + 320

392 = 320 × 1 + 72

320 = 72 × 4 + 32

72 = 32 × 2 + 8

32 = 8 × 4 + 0

as the remainder is zero, divisor 8 is the HCF