Question

3. Find the HCF of the following pair of integers and express it as a linear combination of them,
(i) 963 and 657​

Answer 1

Answer:

963=657*1+306

657=306*2+45

306=45*6+36

45=36*1+9

36=9*4+0

hence HCF is 9

Answer 2

$\huge \fbox \red{Solution:}$

By applying Euclid’s division lemma on 963 and 657, we get

963 = 657 x 1 + 306………. (1)

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

657 = 306 x 2 + 45………… (2)

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

306 = 45 x 6 + 36…………. (3)

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

45 = 36 x 1 + 9…………… (4)

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

36 = 9 x 4 + 0……………. (5)

Thus, we can conclude the H.C.F. = 9.

Now, in order to express the found HCF as a linear combination of 963 and 657, we perform

9 = 45 – 36 x 1 [from (4)]

= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6 [from (3)]

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

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

= 657 x 7 – 306 x 15

= 657 x 7 – [963 – 657 x 1] x 15 [from (1)]

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

= 657 x 22 – 963 x 15.

$\fbox\orange{Thanks}$