Question

use Euclid's division algorithm to find the HCF of 887 and 963​

Answer 1

Given :

• 887 and 963

To find :

• HCF of 887 and 963 by Euclid's division algorithm

Step-by-step explanation:

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 ,

Start with a larger integer , that is 963,

Applying the Euclid's division lemma to 963 and 887, we get

963 = 887 x 1 + 76

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

887 = 76 x 11 + 51

We consider the new divisor 76 and remainder 51 and apply the division lemma to get

76 = 51 x 1 + 25

We consider the new divisor 51 and remainder 25 and apply the division lemma to get

51 = 25 x 2 + 1

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

25 = 1 x 25 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 1 is the HCF of 963 and 887.