Find the HCF of the pair of integers and express it as a linear combin

1.	Find the HCF of the pair of integers and express it as a linear combination of them 693 and 657.
Answer» 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 (5)] = 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.

Find the HCF of the pair of integers and express it as a linear combination of them 693 and 657.

Answer»

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 (5)]

= 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.