Find the HCF of the following pairs of integers and express it as a linear combination of them.
(i) 963 and 657
(ii) 592 and 252
(iii) 506 and 1155
(iv) 1288 and 575
(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$