Find the H.C.F of the following pairs of integers and express it as a linear combination of them.

• (i) 963 and 657
• (ii) 592 and 252
• (iii) 506 and 1155
• (iv) 1288 and 575

To find the highest common factor (H.C.F.) of pairs of integers and express it as a linear combination, we can use the Euclidean algorithm. This method not only helps us determine the H.C.F. but also allows us to express it in the form of a linear combination of the two integers involved. Let's break this down step by step for each pair of integers you've provided.

Finding H.C.F. and Linear Combinations

1. H.C.F. of 963 and 657

We start with the Euclidean algorithm:

• 963 = 657 × 1 + 306
• 657 = 306 × 2 + 45
• 306 = 45 × 6 + 36
• 45 = 36 × 1 + 9
• 36 = 9 × 4 + 0

When we reach a remainder of 0, the last non-zero remainder is the H.C.F. Here, the H.C.F. is 9.

Next, we express 9 as a linear combination:

• 9 = 45 - 1 × 36
• 36 = 306 - 6 × 45
• Substituting gives: 9 = 45 - 1 × (306 - 6 × 45) = 7 × 45 - 1 × 306
• 45 = 657 - 2 × 306
• Substituting again: 9 = 7 × (657 - 2 × 306) - 1 × 306 = 7 × 657 - 15 × 306
• Finally, 306 = 963 - 1 × 657: 9 = 7 × 657 - 15 × (963 - 1 × 657) = 22 × 657 - 15 × 963

Thus, we can express 9 as:

9 = 22 × 657 - 15 × 963

2. H.C.F. of 592 and 252

Applying the Euclidean algorithm:

• 592 = 252 × 2 + 88
• 252 = 88 × 2 + 76
• 88 = 76 × 1 + 12
• 76 = 12 × 6 + 4
• 12 = 4 × 3 + 0

The H.C.F. is 4.

Now, we express 4 as a linear combination:

• 4 = 76 - 6 × 12
• 12 = 88 - 1 × 76
• Substituting gives: 4 = 76 - 6 × (88 - 1 × 76) = 7 × 76 - 6 × 88
• 76 = 252 - 2 × 88: 4 = 7 × (252 - 2 × 88) - 6 × 88 = 7 × 252 - 20 × 88
• 88 = 592 - 2 × 252: 4 = 7 × 252 - 20 × (592 - 2 × 252) = 47 × 252 - 20 × 592

Thus, we can express 4 as:

4 = 47 × 252 - 20 × 592

3. H.C.F. of 506 and 1155

Using the Euclidean algorithm:

• 1155 = 506 × 2 + 143
• 506 = 143 × 3 + 77
• 143 = 77 × 1 + 66
• 77 = 66 × 1 + 11
• 66 = 11 × 6 + 0

The H.C.F. is 11.

Now, expressing 11 as a linear combination:

• 11 = 77 - 1 × 66
• 66 = 143 - 1 × 77: 11 = 77 - 1 × (143 - 1 × 77) = 2 × 77 - 1 × 143
• 77 = 506 - 3 × 143: 11 = 2 × (506 - 3 × 143) - 1 × 143 = 2 × 506 - 7 × 143
• 143 = 1155 - 2 × 506: 11 = 2 × 506 - 7 × (1155 - 2 × 506) = 16 × 506 - 7 × 1155

Thus, we can express 11 as:

11 = 16 × 506 - 7 × 1155

4. H.C.F. of 1288 and 575

Applying the Euclidean algorithm:

• 1288 = 575 × 2 + 138
• 575 = 138 × 4 + 25
• 138 = 25 × 5 + 13
• 25 = 13 × 1 + 12
• 13 = 12 × 1 + 1
• 12 = 1 × 12 + 0

The H.C.F. is 1.

Now, expressing 1 as a linear combination:

• 1 = 13 - 1 × 12
• 12 = 25 - 1 × 13: 1 = 13 - 1 × (25 - 1 × 13) = 2 × 13 - 1 × 25
• 13 = 138 - 5 × 25: 1 = 2 × (138 - 5 × 25) - 1 × 25 = 2 × 138 - 11 ×