There is a quick and easy way to work out the Extended Euclidean Algorithm with pen and paper.

It involving creating a grid like this:

```--+--+--+--+--+--+- ... -+----
Q:| 1| 0|QO|Q1|Q2|  ...  |
--+--+--+--+--+--+- ... -+----
P:| 0| 1|P0|P1|P2|  ...  |
--+--+--+--+--+--+- ... -+----
q:|  |  |qo|q1|q2|  ...  |qn|
--+--+--+--+--+--+- ... -+----
r:|  | a| b|r0|r1|  ...  |rn|
--+--+--+--+--+--+- ... -+----
r:|  |r0|r1|r2|r3|  ...
--+--+--+--+--+--+- ... -+----
```

Where a and b correspond to a and b on Xamot's wu, ri is the remainder of ri-2/ri-1 (consider a and b r-2 and r-1), and qi the quotient of the same division.

Now the Q and P rows correspond roughly to the x's and y's in Xamot's wu. The calculation for them is as follows:

Pi=qi*Pi-1+Pi-2
Qi=qi*Qi-1+Qi-2

The way to proceed is as follows, we usually perform the simple Euclid's Algorithm first:

```--+--+--+--+--+--+--+
q:|  |  | 1| 1| 2|  |
--+--+--+--+--+--+--+
r:|  |12| 7| 5| 2| 1|
--+--+--+--+--+--+--+
r:|  | 5| 2| 1|  |  |
--+--+--+--+--+--+--+
```

Then we proceed with Qi's and Pi's

```--+--+--+--+--+--+--+
Q | 1| 0| 1| 1| 3|
--+--+--+--+--+--+--+
P | 0| 1| 1| 2| 5|
--+--+--+--+--+--+--+
q:|  |  | 1| 1| 2|  |
--+--+--+--+--+--+--+
r:|  |12| 7| 5| 2| 1|
--+--+--+--+--+--+--+
r:|  | 5| 2| 1|  |  |
--+--+--+--+--+--+--+```

So the final Q's and P's are 3 and 5, yielding the Bezout's Identity:

3*12+(-5)*7=1 (signs for Qi and Pi alternate, one is positive for even i's and negative for odd; and the other is the opposite)

Notice that calculating Pi and Qi is really quick, it involves looking up their previous values and qi just below.

As usual, furher help is granted by msg'ing me ;-)