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
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
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 x 1 + 306.
Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306
657 = 306 x 2 + 45.
Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 45
306 = 45 x 6 + 36.
Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36
45 = 36 x 1 + 9.
Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9
36 = 9 x 4 + 0.
Therefore, H.C.F. = 9.
Now, 9 = 45 – 36 x 1
= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6
= 45 x 7 – 306 x 1 = [657 -306 x 2] x 7 – 306 x 1
= 657 x 7 – 306 x 14 – 306 x 1
= 657 x 7 – 306 x 15
= 657 x 7 – [963 – 657 x 1] x 15
= 657 x 7 – 963 x 15 + 657 x 15
= 657 x 22 - 963 x 15
Hence, obtained.
(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 x 2 + 88
Since remainder ≠ 0, apply division lemma on divisor 252 and remainder 88
252 = 88 x 2 + 76
Since remainder ≠ 0, apply division lemma on divisor 88 and remainder 76
88 = 76 x 1 + 12
Since remainder ≠ 0, apply division lemma on divisor 76 and remainder 12
76 = 12 x 6 + 4
Since remainder ≠ 0, apply division lemma on divisor 12 and remainder 4
12 = 4 x 3 + 0.
Therefore, H.C.F. = 4
Now, 4 = 76 – 12 x 6
= 76 – 88 – 76 x 1 x 6
= 76 – 88 x 6 + 76 x 6
= 76 x 7 – 88 x 6
= 252 – 88 x 2 x 7 – 88 x 6
= 252 x 7- 88 x 14- 88 x 6
= 252 x 7- 88 x 20
= 252 x 7 – 592 – 252 x 2 x 20
= 252 x 7 – 592 x 20 + 252 x 40
= 252 x 47 – 592 x 20
= 252 x 77 + 592 x (-20)
Hence obtained.
(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 x 2 + 143.
Since remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
506 = 143 x 3 + 77.
Since remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
143 = 77 x 1 + 66.
Since remainder ≠ 0, apply division lemma on divisor 77 and remainder 66
77 = 66 x 1 + 11.
Since remainder ≠ 0, apply division lemma on divisor 66 and remainder 11
66 = 11 x 6 + 0.
Therefore, H.C.F. = 11.
Now, 11 = 77 – 66 x 1 = 77—[143 – 77 x 1] x 1
= 77 – 143 x 1 + 77 x 1
= 77 x 2 – 143 x 1
= [506 – 143 x 3] x 2 – 143 x 1
= 506 x 2 – 143 x 6 – 143 x 1
= 506 x 2 – 143 x 7 = 506 x 2 – [1155 – 506 x 2] x 7 = 506 x 2 – 1155 x 7+ 506 x 14
= 506 x 16 - 1155 x 7
Hence obtained.
(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 x 2+ 138.
Since remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
575 = 138 x 4 + 23.
Since remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
138 = 23 x 6 + 0.
Therefore, H.C.F. = 23.
Now, 23 = 575 – 138 x 4 = 575 - [1288 – 575 x 2] x 4
= 575 - 1288 x 4 + 575 x 8
= 575 x 9 - 1288 x 4
Hence, obtained.
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 x 1 + 306.
Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306
657 = 306 x 2 + 45.
Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 45
306 = 45 x 6 + 36.
Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36
45 = 36 x 1 + 9.
Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9
36 = 9 x 4 + 0.
Therefore, H.C.F. = 9.
Now, 9 = 45 – 36 x 1
= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6
= 45 x 7 – 306 x 1 = [657 -306 x 2] x 7 – 306 x 1
= 657 x 7 – 306 x 14 – 306 x 1
= 657 x 7 – 306 x 15
= 657 x 7 – [963 – 657 x 1] x 15
= 657 x 7 – 963 x 15 + 657 x 15
= 657 x 22 - 963 x 15
Hence, obtained.
(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 x 2 + 88
Since remainder ≠ 0, apply division lemma on divisor 252 and remainder 88
252 = 88 x 2 + 76
Since remainder ≠ 0, apply division lemma on divisor 88 and remainder 76
88 = 76 x 1 + 12
Since remainder ≠ 0, apply division lemma on divisor 76 and remainder 12
76 = 12 x 6 + 4
Since remainder ≠ 0, apply division lemma on divisor 12 and remainder 4
12 = 4 x 3 + 0.
Therefore, H.C.F. = 4
Now, 4 = 76 – 12 x 6
= 76 – 88 – 76 x 1 x 6
= 76 – 88 x 6 + 76 x 6
= 76 x 7 – 88 x 6
= 252 – 88 x 2 x 7 – 88 x 6
= 252 x 7- 88 x 14- 88 x 6
= 252 x 7- 88 x 20
= 252 x 7 – 592 – 252 x 2 x 20
= 252 x 7 – 592 x 20 + 252 x 40
= 252 x 47 – 592 x 20
= 252 x 77 + 592 x (-20)
Hence obtained.
(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 x 2 + 143.
Since remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
506 = 143 x 3 + 77.
Since remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
143 = 77 x 1 + 66.
Since remainder ≠ 0, apply division lemma on divisor 77 and remainder 66
77 = 66 x 1 + 11.
Since remainder ≠ 0, apply division lemma on divisor 66 and remainder 11
66 = 11 x 6 + 0.
Therefore, H.C.F. = 11.
Now, 11 = 77 – 66 x 1 = 77—[143 – 77 x 1] x 1
= 77 – 143 x 1 + 77 x 1
= 77 x 2 – 143 x 1
= [506 – 143 x 3] x 2 – 143 x 1
= 506 x 2 – 143 x 6 – 143 x 1
= 506 x 2 – 143 x 7 = 506 x 2 – [1155 – 506 x 2] x 7 = 506 x 2 – 1155 x 7+ 506 x 14
= 506 x 16 - 1155 x 7
Hence obtained.
(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 x 2+ 138.
Since remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
575 = 138 x 4 + 23.
Since remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
138 = 23 x 6 + 0.
Therefore, H.C.F. = 23.
Now, 23 = 575 – 138 x 4 = 575 - [1288 – 575 x 2] x 4
= 575 - 1288 x 4 + 575 x 8
= 575 x 9 - 1288 x 4
Hence, obtained.
