Find the HCF of 506 and 1155 and Express it as a Linear Combination

Video Explanation

Watch the video below to understand the complete solution step by step:

Solution

Question: Find the HCF of the following pairs of integers and express it as a linear combination of them:

506 and 1155

Step 1: Use Euclid’s Division Algorithm

1155 = 506 × 2 + 143

506 = 143 × 3 + 77

143 = 77 × 1 + 66

77 = 66 × 1 + 11

66 = 11 × 6 + 0

Since the remainder is zero,

∴ HCF (506, 1155) = 11

Step 2: Express HCF as a Linear Combination

11 = 77 − 66

11 = 77 − (143 − 77)

11 = 2 × 77 − 143

11 = 2 × (506 − 143 × 3) − 143

11 = 2 × 506 − 7 × 143

11 = 2 × 506 − 7 × (1155 − 506 × 2)

11 = 16 × 506 − 7 × 1155

Final Answer

∴ The HCF of 506 and 1155 is 11 and it can be expressed as:

11 = 16 × 506 − 7 × 1155

Conclusion

Thus, using Euclid’s division algorithm, we found the HCF of 506 and 1155 and expressed it as a linear combination of the given integers.