3. 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
4. Express the HCF of 468 and 222 as 468x + 222u where x,y are integers in two different
Answers
Answer:
(i) 963 and 6567 By applying Euclid’s division lemma 963 = 657 × 1 + 306 …(i) Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306 657 = 306 × 2 + 45 ….. (ii) Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 4 306 = 45 × 6 + 36 …..(iii) Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36 45 = 36 × 1 + 9 …… (iv) Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9 36 = 9 × 4 + 0 ∴ HCF = 9 Now 9 = 45 – 36 × 1 [from (iv)] = 45 – [306 – 45 × 6] × 1 [from (iii)] = 45 – 306 × 1 + 45 × 6 = 45 × 7 – 306 × 1 = 657 × 7 – 306 × 14 – 306 × 1 [from (ii)] = 657 × 7 – 306 × 15 = 657 × 7 – [963 – 657 × 1] × 15 [from (i)] = 657 × 22 – 963 × 15 (ii) 595 and 252 By applying Euclid’s division lemma 595 = 252 × 2 + 91 ….. (i) Since remainder ≠ 0, apply division lemma on divisor 252 and remainder 91 252 = 91 × 2 + 70 …. (ii) Since remainder ≠ 0, apply division lemma on divisor 91 and remainder 70 91 = 70 × 1 + 21 ….(iii) Since remainder ≠ 0, apply division lemma on divisor 70 and remainder 20 70 = 21 × 3 + 7 …..(iv) Since remainder ≠ 0, apply division lemma on divisor 21 and remainder 7 21 = 7 × 3 + 0 H.C.F = 7 Now, 7 = 70 – 21 × 3 [from (iv)] = 70 – [90 – 70 × 1] × 3 [from (iii)] = 70 – 91 × 3 + 70 × 3 = 70 × 4 – 91 × 3 = [252 – 91 × 2] × 4 – 91 × 3 [from (ii)] = 252 × 4 – 91 × 8 – 91 × 3 = 252 × 4 – 91 × 11 = 252 × 4 – [595 – 252 × 2] × 11 [from (i)] = 252 × 4 – 595 × 11 + 252 × 22 = 252 × 6 – 595 × 11 (iii) 506 and 1155 By applying Euclid’s division lemma 1155 = 506 × 2 + 143 …. (i) Since remainder ≠ 0, apply division lemma on division 506 and remainder 143 506 = 143 × 3 + 77 ….(ii) Since remainder ≠ 0, apply division lemma on division 143 and remainder 77 143 = 77 × 1 + 56 ….(iii) Since remainder ≠ 0, apply division lemma on division 77 and remainder 66 77 = 66 × 1 + 11 …(iv) Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9 66 = 11 × 6 + 0 ∴ HCF = 11 Now, 11 = 77 – 6 × 11 [from (iv)] = 77 – [143 – 77 × 1] × 1 [from (iii)] = 77 – 143 × 1 – 77 × 1 = 77 × 2 – 143 × 1 = [506 – 143 × 3] × 2 – 143 × 1 [from (ii)] = 506 × 2 – 143 × 6 – 143 × 1 = 506 × 2 – 143 × 7 = 506 × 2 – [1155 – 506 × 27 × 7] [from (i)] = 506 × 2 – 1155 × 7 + 506 × 14 = 506 × 16 – 115 × 7 (iv) 1288 and 575 By applying Euclid’s division lemma 1288 = 575 × 2 + 138 …(i) Since remainder ≠ 0, apply division lemma on division 575 and remainder 138 575 = 138 × 1 + 23 …(ii) Since remainder ≠ 0, apply division lemma on division 138 and remainder 23 …(iii) ∴ HCF = 23 Now, 23 = 575 – 138 × 4 [from (ii)] = 575 – [1288 – 572 × 2] × 4 [from (i)] = 575 – 1288 × 4 + 575 × 8 = 575 × 9 – 1288 × 4
To show: HCF of 468 and 222 as 468x + 222y in two different ways. Now, we need to express the HCF of 468 and 222 as 468x + 222y where x and y are any two integers. Therefore, the HCF of 468 and 222 is written in the form of 468x + 222y where, -9 and 19 are the two integers.