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.
Most of the speedups of the Euclidean Algorithm described in Knuth's Art of Computer Programming v2 work here also.