So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination.
For example, a problem is to express the gcd(117,213) as a linear combination of these integers.
213 = 117 * 1 + 96
117 = 96 * 1 + 21
96 = 21 * 4 + 12
21 = 12 * 1 + 9
12 = 9 * 1 + 3
So gcd(117,213) = 3.
Going back, it's time to rewrite the equations as an expression of the remainder.
96 = 213 - 117
21 = 117 - 96
12 = 96 - 4 * 21
9 = 21 - 12
3 = 12 - 9
Then, as I understand it, you work your way up and substitute.
96 = 213 - 117
21 = 117 - (213 - 117) = -213 + 2 * 117
12 = (213 - 117) - 4 * (-213 + 2 * 117) = 5 * 213 - 9 * 117
9 = (-213 + 2 * 117) - (5 * 213 - 9 * 117) = -6 * 213 + 11 * 117
3 = (5 * 213 - 9 * 117) - (-6 * 213 + 11 * 117) = 11 * 213 - 20 * 117
My problem is, I don't understand how to simplify. Like in the step I bolded above, where the heck are the 5 and 9 coming from?
You have: 1) 1 copy of $213$ on the L.H parenthesis, just appearing as a $213$ , and $4$ copies of $213$ on the right parenthesis, appearing as $-213 (-4)$ (notice the two minueses cancel out in the product), for a total of $5$ copies of $213$. 2) For $117$ .Check something similar for the number of copies of 117 in the two parentheses.