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
Answers
SOLUTION :
(i) First ,we need to find the H.C.F. of 963 and 657
Here, 963 > 657
Let a = 963 and b= 657
963 = 657 x 1 + 306………….(1)
[By applying division lemma, a = bq + r]
Here, remainder = 306 ≠ 0, so take new dividend as 657 and new divisor as 306
Let a = 657 and b= 306
657 = 306 x 2 + 45..................(2)
Here, remainder = 45 ≠ 0, so take new dividend as 306 and new divisor as 45
Let a = 306 and b= 45
306 = 45 x 6 + 36………………(3)
Here, remainder = 36 ≠ 0, so take new dividend as 45 and new divisor as 36.
Let a = 45 and b= 36
45 = 36 x 1 + 9…………….(4)
Here, remainder = 9 ≠ 0, so take new dividend as 36 and new divisor as 9
Let a = 36 and b= 9
36 = 9 x 4 + 0.................(5)
Here, remainder is zero and divisor is 9.
Hence ,H.C.F. of 963 and 657 is 9.
H.C.F. = 9.
Now, 9 = 45 - 36 x 1
= 45 – [306 – 45 x 6] x 1
[Substituting 306 - 45 x 6 = 36 from eq 3]
= 45 – 306 x 1 + 45 x 6
= 45 + 45 x 6 – 306 x 1
= 45 x 7 – 306 x 1
= [657 - 306 x 2] x 7 – 306 x 1
[Substituting 657 - 306 x 2 = 45 from eq 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
[Substituting 963 – 657 x 1 = 306 from eq 1]
= 657 x 7 – 963 x 15 + 657 x 15
= 657 x 7 + 657 x 15 - 963 x 15
9 = 657 x 22 - 963 x 15.
Hence,the linear combination is 9 = 657 x 22 - 963 x 15.
(ii) First , we need to find the H.C.F. of 592 and 252.
Here, 592 > 252
Let a = 592 and b= 252
592 = 252 x 2 + 88………….(1)
[By applying division lemma, a = bq + r]
Here, remainder = 88 ≠ 0, so take new dividend as 252 and new divisor as 88.
Let a = 252 and b= 88
252 = 88 x 2 + 76………….(2)
[By applying division lemma, a = bq + r]
Here, remainder = 76 ≠ 0, so take new dividend as 88 and new divisor as 76
Let a = 88 and b= 76
88 = 76 x 1 + 12………….(3)
[By applying division lemma, a = bq + r]
Here, remainder = 12 ≠ 0, so take new dividend as 76 and new divisor as 12.
Let a = 76 and b= 12
76 = 12 x 6 + 4………….(4)
[By applying division lemma, a = bq + r]
Here, remainder = 14 ≠ 0, so take new dividend as 12 and new divisor as 4.
Let a = 12 and b= 4
12 = 4 x 3 + 0….……….(5)
[By applying division lemma, a = bq + r]
Here, remainder is zero and divisor is 4
Hence ,H.C.F. of 592 and 252 is 4.
H.C.F. = 4.
Now, 4 = 76 – 12 x 6
[Substituting 76 – 12 x 6 = 4 from eq 4]
= 76 – 88 – 76 x 1 x 6
[Substituting 88 – 76 x 1 = 12 from eq 3]
= 76 – 88 x 6 + 76 x 6
= 76 + 76 x 6 – 88 x 6
= 76 x 7 – 88 x 6
= 252 – 88 x 2 x 7 – 88 x 6
[Substituting 252 – 88 x 2 = 76 from eq 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
[Substituting 592 – 252 x 2 = 88 from eq 1]
= 252 x 7 – 592 x 20 + 252 x 40
= 252 x 7 + 252 x 40 – 592 x 20
= 252 x 47 – 592 x 20
4 = 252 x 47 + 592 x (-20)
Hence , the linear combination is 4 = 252 x 47 + 592 x (-20).
HOPE THIS ANSWER WILL HELP YOU…