Find the HCF of the pair of integers and express it as a linear combin

1.	Find the HCF of the pair of integers and express it as a linear combination of them 506 and 1155.
Answer» 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) Thus, we can conclude the H.C.F. = 11. Now, in order 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

Find the HCF of the pair of integers and express it as a linear combination of them 506 and 1155.

Answer»

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)

Thus, we can conclude the H.C.F. = 11.

Now, in order 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