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
Answers
HCF is (i) 9 (ii) 4 (iii) 11 (iv) 23
Step-by-step explanation:
(i) 963 & 657
By applying Euclid’s division lemma on 963 and 657, we get
963 = 657 x 1 + 306 ---- (1)
As the remainder ≠ 0, apply division lemma on divisor 657 and remainder 306
657 = 306 x 2 + 45 ---- (2)
As the remainder ≠ 0, apply division lemma on divisor 306 and remainder 45
306 = 45 x 6 + 36 ---- (3)
As the remainder ≠ 0, apply division lemma on divisor 45 and remainder 36
45 = 36 x 1 + 9 ---- (4)
As the remainder ≠ 0, apply division lemma on divisor 36 and remainder 9
36 = 9 x 4 + 0 ---- (5)
Therefore H.C.F. = 9.
To express the found HCF as a linear combination of 963 and 657, we perform
9 = 45 – 36 x 1 [from (5)]
= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6 [from (3)]
= 45 x 7 – 306 x 1 = [657 -306 x 2] x 7 – 306 x 1 [from (2)]
= 657 x 7 – 306 x 14 – 306 x 1
= 657 x 7 – 306 x 15
= 657 x 7 – [963 – 657 x 1] x 15 [from (1)]
= 657 x 7 – 963 x 15 + 657 x 15
= 657 x 22 – 963 x 15.
(ii) 592 and 252
By applying Euclid’s division lemma on 592 and 252, we get
592 = 252 x 2 + 88 ---- (1)
As the remainder ≠ 0, apply division lemma on divisor 252 and remainder 88
252 = 88 x 2 + 76 ---- (2)
As the remainder ≠ 0, apply division lemma on divisor 88 and remainder 76
88 = 76 x 1 + 12----(3)
As the remainder ≠ 0, apply division lemma on divisor 76 and remainder 12
76 = 12 x 6 + 4 ----(4)
Since the remainder ≠ 0, apply division lemma on divisor 12 and remainder 4
12 = 4 x 3 + 0 ----(5)
Therefore H.C.F. = 4.
To express the found HCF as a linear combination of 592 and 252, we perform
4 = 76 – 12 x 6 [from (4)]
= 76 – [88 – 76 x 1] x 6 [from (3)]
= 76 – 88 x 6 + 76 x 6
= 76 x 7 – 88 x 6
= [252 – 88 x 2] x 7 – 88 x 6 [from (2)]
= 252 x 7- 88 x 14- 88 x 6
= 252 x 7- 88 x 20
= 252 x 7 – [592 – 252 x 2] x 20 [from (1)]
= 252 x 7 – 592 x 20 + 252 x 40
= 252 x 47 – 592 x 20
= 252 x 47 + 592 x (-20)
(iii) 506 and 1155
By applying Euclid’s division lemma on 506 and 1155, we get
1155 = 506 x 2 + 143 ---- (1)
As the remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
506 = 143 x 3 + 77 ---- (2)
As the remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
143 = 77 x 1 + 66 ---- (3)
Since the remainder ≠ 0, apply division lemma on divisor 77 and remainder 66
77 = 66 x 1 + 11 ---- (4)
As the remainder ≠ 0, apply division lemma on divisor 66 and remainder 11
66 = 11 x 6 + 0 ---- (5)
Therefore H.C.F. = 11.
To express the found HCF as a linear combination of 506 and 1155, we perform
11 = 77 – 66 x 1 [from (4)]
= 77 – [143 – 77 x 1] x 1 [from (3)]
= 77 – 143 x 1 + 77 x 1
= 77 x 2 – 143 x 1
= [506 – 143 x 3] x 2 – 143 x 1 [from (2)]
= 506 x 2 – 143 x 6 – 143 x 1
= 506 x 2 – 143 x 7
= 506 x 2 – [1155 – 506 x 2] x 7 [from (1)]
= 506 x 2 – 1155 x 7+ 506 x 14
= 506 x 16 – 1155 x 7
(iv) 1288 and 575
By applying Euclid’s division lemma on 1288 and 575, we get
1288 = 575 x 2+ 138 ---- (1)
As the remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
575 = 138 x 4 + 23 ---- (2)
As the remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
138 = 23 x 6 + 0 ---- (3)
Therefore H.C.F. = 23.
To express the found HCF as a linear combination of 1288 and 575, we perform
23 = 575 – 138 x 4 [from (2)]
= 575 – [1288 – 575 x 2] x 4 [from (1)]
= 575 – 1288 x 4 + 575 x 8
= 575 x 9 – 1288 x 4