Find the HCF of 592 and 252 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:

592 and 252

Step 1: Use Euclid’s Division Algorithm

592 = 252 × 2 + 88

252 = 88 × 2 + 76

88 = 76 × 1 + 12

76 = 12 × 6 + 4

12 = 4 × 3 + 0

Since the remainder is zero,

∴ HCF (592, 252) = 4

Step 2: Express HCF as a Linear Combination

4 = 76 − 12 × 6

4 = 76 − (88 − 76 × 1) × 6

4 = 7 × 76 − 6 × 88

4 = 7 × (252 − 88 × 2) − 6 × 88

4 = 7 × 252 − 20 × 88

4 = 7 × 252 − 20 × (592 − 252 × 2)

4 = 47 × 252 − 20 × 592

Final Answer

∴ The HCF of 592 and 252 is 4 and it can be expressed as:

4 = 47 × 252 − 20 × 592

Conclusion

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