Find the HCF of the following pairs of integers and express it as a linear combination of them
(i) 963 & 657 (ii) 592 & 252
(iii) 506 & 1155 (iv) 1288 & 575
(i) Using Euclid’s Division Lemma
a = bq + r, (o ≤r<b)
963 = 657×1 + 306
657 = 306×2 + 45
306 = 45×6+36
45 = 36×1+9
36 = 9×4+0
∴ HCF (657, 963) = 9
(ii) Using Euclid’s Division Lemma
a = bq + r, (o ≤r<b)
592 = 252×2+88
252 = 88×2+76
88 = 76×1+12
76 = 12×6+4
12 = 4×3+0
∴ HCF (657, 963) = 4
(iii) Using Euclid’s Division Lemma
a = bq + r, (o ≤r<b)
1155 = 506×2+143
506 = 143×3+77
143 = 77×1+66
77 = 66×1+11
66 = 11×6+0
∴ HCF (657, 963) = 11
(iv) Using Euclid’s Division Lemma
a = bq + r, (o ≤r<b)
1288 = 575×2+138
575 = 138×4+23
138 = 23×6+0
∴ HCF (657, 963) = 23