Question

find HCF and express lin linear combination of 963 and 657 by using euclid algorithm. ​

Answer 1

Answer:

Step-by-step explanation:

We need to find the H.C.F. of 963 and 657 and express it as a linear combination of 963 and 657. By applying Euclid’s division lemma, 963 = 657 x 1 + 306.

Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306

657 = 306 x 2 + 45.

Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 45

306 = 45 x 6 + 36.

Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36

45 = 36 x 1 + 9.

Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9

36 = 9 x 4 + 0.

Therefore, H.C.F. = 9.

Now, 9 = 45 – 36 x 1

= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6

= 45 x 7 – 306 x 1 = [657 -306 x 2] x 7 – 306 x 1

= 657 x 7 – 306 x 14 – 306 x 1

= 657 x 7 – 306 x 15

= 657 x 7 – [963 – 657 x 1] x 15

= 657 x 7 – 963 x 15 + 657 x 15

= 657 x 22 – 963 x 15.

Hence, obtained.