Question

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

Answer 1

(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

Since remainder, apply division lemma on divisor 657 and remainder 306

Since remainder, apply division lemma on divisor 306 and remainder 45

Since remainder, apply division lemma on divisor 45 and remainder 36

Since remainder, apply division lemma on divisor 36 and remainder 9

Therefore, H.C.F. = 9.

Now,

(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, apply division lemma on divisor 252 and remainder 88

252 = 88×2+76

Since remainder, apply division lemma on divisor 88 and remainder 76

88 = 76×1+12

Since remainder, apply division lemma on divisor 76 and remainder 12

76 = 12×6+4

Since remainder, apply division lemma on divisor 12 and remainder 4

12 = 4×3+0.

Therefore, H.C.F. = 4.

Now,
$$\begin{gathered} 4=76-12\times 6 \\ =76-\left[88-76\times 1\right]\times 6 \\ =76-88\times 6+76\times 6 \\ =76\times 7-88\times 6 \\ =\left(252-88\times 2\right)\times 7-88\times 6 \\ =252\times 7-88\times 14-88\times 6 \\ =252\times 7-88\times 20 \\ =252\times 7-\left[592-252\times 2\right]\times 20 \\ =252\times 7-592\times 20+252\times 40 \\ =252\times 47-592\times 20 \\ =\boxed{252\times 47+592\times \left(-20\right)} \end{gathered}$$

(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

Since remainder, apply division lemma on divisor 506 and remainder 143

Since remainder, apply division lemma on divisor 143 and remainder 77

Since remainder, apply division lemma on divisor 77 and remainder 66

Since remainder, apply division lemma on divisor 66 and remainder 11

Therefore, H.C.F. = 11.

Now,

(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

Since remainder, apply division lemma on divisor 575 and remainder 138

Since remainder, apply division lemma on divisor 138 and remainder 23

Therefore, H.C.F. = 23.

Now,