Euclid algorithm - linear combination I've been taught that Euclids algorithm for $(a,b), a > b $ can be used to find $x,y$ such that $ax + by = d$, where $d$ is their GCD. However, the only method we have used to obtain this is by making a table of all the quotients and then following the set of recursions:
$x_i=x_{i-2} - q_ix_{i-1},
y_i=y_{i-2} - q_iy_{i-1}$
until we reach the last quotient.
My question is, is there a faster way to find $x$ and $y$?

You could use Euclidean algorithm "backwards" to get the general solution. Let's divide out the GCD to get a $1$ on the right hand side.
Example: $5x+13y=1$ Then $13=2*5+3$ then $5=1*3+2$ then $3=1*2+1$ backwards: $2*3-1*5=1$ then $3-(5-1*3)=1$ then $2(13-2*5)-1*5=1$ to get $2*13-5*5=1$ amd so we find a solution $x=-5,y=2$ introducing parameter $t$ to find a general set: $x=13t-5,y=-5t+2$ Watch how I took opposite signs of the t-coefficients!
I found using Euclid's algorithm backwards a very fast way to get a general set of solutions in parametric form
