Question

Find the hcf of 1208 & 575 using Euclid's division lemma

Answer 1

Hi ,

We know that

_________________________

Euclid's division algorithm:

Let a and b be any two positive

integers then there exists two unique

whole numbers q and r such that

a = bq + r ,

Where, 0 ≤ r < b

__________________________

Applying division algorithm to 1288

and 575

1288 = 575 × 2 + 138

575 = 138 × 4 + 23

138 = 23 × 6 + 0

The remainder has now become

zero, so our procedure stops .

Since the divisor at this stage is 23.

The HCF of 1288 and 575 is 23

I hope this helps you.

PLS MARK ME AS BRAINLIST PLS

Answer 2

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, 1208 > 575

Start with a larger integer , that is 1208.

Applying the Euclid's division lemma to 1208 and 575, we get

1208 = 575 x 2 + 58

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

575 = 58 x 9 + 53

We consider the new divisor 58 and remainder 53 and apply the division lemma to get

58 = 53 x 1 + 5

We consider the new divisor 53 and remainder 5 and apply the division lemma to get

53 = 5 x 10 + 3

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

5 = 3 x 1 + 2

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

3 = 2 x 1 + 1

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

2 = 1 x 2 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 1 is the HCF of 1208 and 575.