Find the HCF of the following pairs of integers and express it as a linear combination of them.

Solution:

(i) 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 \times 1+306$

Since remainder $\neq 0$, apply division lemma on divisor 657 and remainder 306

$657=306 \times 2+45$

Since remainder $\neq 0$, apply division lemma on divisor 306 and remainder 45

$306=45 \times 6+36$

Since remainder $\neq 0$, apply division lemma on divisor 45 and remainder 36

$45=36 \times 1+9$

Since remainder $\neq 0$, apply division lemma on divisor 36 and remainder 9

$36=9 \times 4+0$

Therefore, H.C.F. = 9.

Now,

$9=45-36 \times 1$

$=45-[306-45 \times 6] \times 1$

$=45-306 \times 1+45 \times 6$

$=45 \times 7-306 \times 1$

$=[657-306 \times 2] \times 7-306 \times 1$

$=657 \times 7-306 \times 14-306 \times 1$

$=657 \times 7-306 \times 15$

$=657 \times 7-[963-657 \times 1] \times 15$

$=657 \times 7-963 \times 15+657 \times 15$

$=657 \times 22-963 \times 15 .$

(ii) We need to find the H.C.F. of 592 and 252 and express it as a linear combination of 592 and 252.

By applying Euclid’s division lemma

592 = 252×2+88

Since remainder $\neq 0$, apply division lemma on divisor 252 and remainder 88

252 = 88×2+76

Since remainder $\neq 0$, apply division lemma on divisor 88 and remainder 76

88 = 76×1+12

Since remainder $\neq 0$, apply division lemma on divisor 76 and remainder 12

76 = 12×6+4

Since remainder $\neq 0$, apply division lemma on divisor 12 and remainder 4

12 = 4×3+0.

Therefore, H.C.F. = 4.

Now,

$4=76-12 \times 6$

$=76-[88-76 \times 1] \times 6$

$=76-88 \times 6+76 \times 6$

$=76 \times 7-88 \times 6$

$=(252-88 \times 2) \times 7-88 \times 6$

$=252 \times 7-88 \times 14-88 \times 6$

$=252 \times 7-88 \times 20$

$=252 \times 7-[592-252 \times 2] \times 20$

$=252 \times 7-592 \times 20+252 \times 40$

$=252 \times 47-592 \times 20$

$=252 \times 47+592 \times(-20)$

(iii) We need to find the H.C.F. of 506 and 1155 and express it as a linear combination of 506 and 1155.

By applying Euclid’s division lemma

$1155=506 \times 2+143$

Since remainder $\neq 0$, apply division lemma on divisor 506 and remainder 143

$506=143 \times 3+77$

Since remainder $\neq 0$, apply division lemma on divisor 143 and remainder 77

$143=77 \times 1+66$

Since remainder $\neq 0$, apply division lemma on divisor 77 and remainder 66

$77=66 \times 1+11$

Since remainder $\neq 0$, apply division lemma on divisor 66 and remainder 11

$66=11 \times 6+0$

Therefore, H.C.F. = 11.

Now,

$11=77-66 \times 1$

$=77-[143-77 \times 1] \times 1$

$=77-143 \times 1+77 \times 1$

$=77 \times 2-143 \times 1$

$=[506-143 \times 3] \times 2-143 \times 1$

$=506 \times 2-143 \times 6-143 \times 1$

$=506 \times 2-143 \times 7$

$=506 \times 2-[1155-506 \times 2] \times 7$

$=506 \times 2-1155 \times 7+506 \times 14$

$=506 \times 16-1155 \times 7 .$

(iv) We need to find the H.C.F. of 1288 and 575 and express it as a linear combination of 1288 and 575.

By applying Euclid’s division lemma

$1288=575 \times 2+138$

Since remainder $\neq 0$, apply division lemma on divisor 575 and remainder 138

$575=138 \times 4+23 .$

Since remainder $\neq 0$, apply division lemma on divisor 138 and remainder 23

$138=23 \times 6+0$

Therefore, H.C.F. = 23.

Now,

$23=575-138 \times 4$

$=575-[1288-575 \times 2] \times 4$

$=575-1288 \times 4+575 \times 8$

$=575 \times 9-1288 \times 4$