Find the HCF of 963 and 657 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:

963 and 657

Step 1: Use Euclid’s Division Algorithm

963 = 657 × 1 + 306

657 = 306 × 2 + 45

306 = 45 × 6 + 36

45 = 36 × 1 + 9

36 = 9 × 4 + 0

Since the remainder is zero,

∴ HCF (963, 657) = 9

Step 2: Express HCF as a Linear Combination

9 = 45 − 36

9 = 45 − (306 − 45 × 6)

9 = 7 × 45 − 306

9 = 7 × (657 − 306 × 2) − 306

9 = 7 × 657 − 15 × 306

9 = 7 × 657 − 15 × (963 − 657)

9 = 22 × 657 − 15 × 963

Final Answer

∴ The HCF of 963 and 657 is 9 and it can be expressed as:

9 = 22 × 657 − 15 × 963

Conclusion

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