Here is a tidy way to solve $ax+by=gcd(a,b)$. Start with the matrix
$$\left(\begin{array}{ccc}
  1&0&a\\
  0&1&b\\
 \end{array}\right)
$$
Suppose $a\ge b$. Then replace row 1 by row 1 minus $t$ times row 2, where $t=\lfloor a/b\rfloor$. Repeat this operation until the last entry in one of the two rows is zero. If the other row is $x,y,d$ then $ax+by=d$ and $d=gcd(a,b)$. This is very simple to program, and avoids the back-substitutions that students find confusing.