How to use the Extended Euclidean Algorithm manually? I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
 A: You may like to check this (Wayback Machine) and this.
Also, there is a well known table method which is very easy and fast for the manual solution. (A link to an older revision of the Wikipedia article which contained the section on table method.)
A: The way to do this is due to Blankinship "A New Version of the Euclidean Algorithm", AMM 70:7 (Sep 1963), 742-745. Say we want $a x + b y = \gcd(a, b)$, for simplicity with positive $a$, $b$ with $a > b$. Set up auxiliary vectors $(x_1, x_2, x_3)$, $(y_1, y_2, y_3)$ and $(t_1, t_2, t_3)$ and keep them such that we always have $x_1 a + x_2 b = x_3$, $y_1 a + y_2 b = y_3$, $t_1 a + t_2 b = t_3$ throughout. The algorithm itself is:
(x1, x2, x3) := (1, 0, a)
(y1, y2, y3) := (0, 1, b)
while y3 <> 0 do
    q := floor(x3 / y3)
    (t1, t2, t3) := (x1, x2, x3) - q * (y1, y2, y3)
    (x1, x2, x3) := (y1, y2, y3)
    (y1, y2, y3) := (t1, t2, t3)

At the end, $x_1 a + x_2 b = x3 = \gcd(a, b)$. It is seen that $x_3$, $y_3$ do as the classic Euclidean algorithm, and easily checked that the invariant mentioned is kept all the time.
One can do away with $x_2$, $y_2$, $t_2$ and recover $x_2$ at the end as $(x_3 - x_1 a) / b$.
A: This is more a comment on the method explained by Bill Dubuque then a proper answer in itself, but I think there is a remark so obvious that I don’t understand that it is hardly ever made in texts discussing the extended Euclidean algorithm. This is the observation that you can save yourself half of the work by computing only one of the Bezout coefficients. In other words, instead of recording for every new remainder $r_i$ a pair of coefficients $k_i,l_i$ so that $r_i=k_ia+l_ib$, you need to record only $k_i$ such that $r_i\equiv k_ia\pmod b$. Once you will have found $d=\gcd(a,b)$ and $k$ such that $d\equiv ka\pmod b$, you can then simply put $l=(d-ka)/b$ to get the other Bezout coefficient. This simplification is possible because the relation that gives the next pair of intermediate coefficients is perfectly independent for the two coefficients: say you have
$$
\begin{aligned}  r_i&=k_ia+l_ib\\ r_{i+1}&=k_{i+1}a+l_{i+1}b\end{aligned}
$$
and Euclidean division gives $r_i=qr_{i+1}+r_{i+2}$, then in order to get
$$
  r_{i+2}=k_{i+2}a+l_{i+2}b
$$
one can take $k_{i+2}=k_i-qk_{i+1}$ and $l_{i+2}=l_i-ql_{i+1}$, where the equation for $k_{i+2}$ does not need $l_i$ or $l_{i+1}$, so you can just forget about the $l$'s. In matrix form, the passage is from
$$
  \begin{pmatrix} r_i&k_i&l_i\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix}
  \quad\text{to}\quad
  \begin{pmatrix} r_{i+2}&k_{i+2}&l_{i+2}\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix}
$$
by subtracting the second row $q$ times from the first, and it is clear that the last two columns are independent, and one might as well just keep the $r$'s and the $k$'s, passing from
$$
  \begin{pmatrix} r_i&k_i\\ r_{i+1}&k_{i+1}\end{pmatrix}
  \quad\text{to}\quad
  \begin{pmatrix} r_{i+2}&k_{i+2}\\ r_{i+1}&k_{i+1}\end{pmatrix}
$$
instead.
A very minor drawback is that the relation $r_i=k_ia+l_ib$ that should hold for every row is maybe a wee bit easier to check by inspection than $r_i\equiv k_ia\pmod b$, so that computational errors could slip in a bit more easily. But really, I think that with some practice this method is just as safe and faster than computing both coefficients. Certainly when programming this on a computer there is no reason at all to keep track of both coefficients.
A final bonus it that in many cases where you apply the extended Euclidean algorithm you are only interested in one of the Bezout coefficients in the first place, which saves you the final step of computing the other one. One example is computing inverse modulo a prime number $p$: if you take $b=p$, and $a$ is not divisible by it, then you know beforehand that you will find $d=1$, and the coefficient $k$ such that $d\equiv ka\pmod p$ is just the inverse of $a$ modulo $p$ that you were after.
