Write the gcd (107,345) as a linear combination of 107 and 345 by using the Euclidian Algorithm

Write the gcd (107,345) as a linear combination of 107 and 345 by using the Euclidian Algorithm.

The correct answer and explanation is :

To write the greatest common divisor (gcd) of 107 and 345 as a linear combination of 107 and 345, we will use the Euclidean algorithm followed by back substitution. The Euclidean algorithm is based on the principle that the gcd of two numbers (a) and (b) is the same as the gcd of (b) and the remainder when (a) is divided by (b).

Step 1: Apply the Euclidean Algorithm

We start with the two numbers, 107 and 345, and apply the Euclidean algorithm:

1. Divide 345 by 107:
   (345 \div 107 = 3) with a remainder of (345 – 3 \times 107 = 345 – 321 = 24). So, (345 = 3 \times 107 + 24).
2. Divide 107 by 24:
   (107 \div 24 = 4) with a remainder of (107 – 4 \times 24 = 107 – 96 = 11). So, (107 = 4 \times 24 + 11).
3. Divide 24 by 11:
   (24 \div 11 = 2) with a remainder of (24 – 2 \times 11 = 24 – 22 = 2). So, (24 = 2 \times 11 + 2).
4. Divide 11 by 2:
   (11 \div 2 = 5) with a remainder of (11 – 5 \times 2 = 11 – 10 = 1). So, (11 = 5 \times 2 + 1).
5. Divide 2 by 1:
   (2 \div 1 = 2) with a remainder of (0). So, (2 = 2 \times 1 + 0), and the remainder is 0, meaning the gcd is 1.

Thus, the gcd of 107 and 345 is 1.

Step 2: Back Substitution

Now that we know the gcd is 1, we can work backward to express 1 as a linear combination of 107 and 345.

• From (11 = 5 \times 2 + 1), we have:
  (1 = 11 – 5 \times 2).
• From (24 = 2 \times 11 + 2), we can substitute (2 = 24 – 2 \times 11) into the equation:
  (1 = 11 – 5 \times (24 – 2 \times 11)).
  Simplifying:
  (1 = 11 – 5 \times 24 + 10 \times 11)
  (1 = 11 \times 11 – 5 \times 24).
• From (107 = 4 \times 24 + 11), we substitute (11 = 107 – 4 \times 24) into the equation:
  (1 = (107 – 4 \times 24) \times 11 – 5 \times 24).
  Simplifying:
  (1 = 11 \times 107 – 44 \times 24 – 5 \times 24)
  (1 = 11 \times 107 – 49 \times 24).
• Finally, from (345 = 3 \times 107 + 24), we substitute (24 = 345 – 3 \times 107) into the equation:
  (1 = 11 \times 107 – 49 \times (345 – 3 \times 107)).
  Simplifying:
  (1 = 11 \times 107 – 49 \times 345 + 147 \times 107)
  (1 = (11 + 147) \times 107 – 49 \times 345)
  (1 = 158 \times 107 – 49 \times 345).

Conclusion

Thus, the gcd of 107 and 345 is 1, and we can express this as a linear combination:

[
1 = 158 \times 107 – 49 \times 345
]

This means that 1 is a linear combination of 107 and 345 with coefficients 158 and -49.