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(9999,11111) as a linear combination of these integers.
11111 = 9999 * 1 + 1112
9999 = 1112 * 8 + 1103
1112 = 1103 * 1 + 9
9 = 5 * 1 + 4
5 = 4 * 1 + 1
So gcd(11111,9999) = 1.
Going back, it's time to rewrite the equations as an expression of the remainder.
1112 = 11111 - 9999
1103 = 9999 - 1112 * 8
9 = 1112 - 1103
5 = 1103 - 122 * 9
4 = 9 -5
1 = 5 -4
Then, as I understand it, you work your way up and substitute.
1 = 5 - 4
1 = 5 - (9 - 5) = ?
My problem is, I don't understand how to simplify. That's as far as I've got. How to do this?!
There is an error at the last but one line: you should divide $1103$ by $9$, not $9$ by $5$.
The systematic way consists in using the Extended Euclidean Algorithm, which gives Bézout's coefficients for every remainder in the Euclidean Algorithm:
$$ \begin{array}{rrrr} r_i & u_i & v_i & q_i\\ \hline 11111 & 1 & 0 & \\ 9999 & 0 & 1 & 1\\ \hline 1103 & -8 & 9 & 1\\ 9 & 9 & -10 & 122 \\ 5 & -1106 & 1229 & 1 \\ 4 & 1115 & -1239 & 1\\ 1 & -2221 & 2468 \\ \hline \end{array} $$
Thus $1=2468\times 9999-2221\times11111$.