Extended Euclidean Algorithm: why does it work? I find myself able to mechanically apply the "extended" Euclidean algorithm to find the gcd of two integers and to write a linear combination by working backwards. However, I do not have a good grasp as to why this works. Artin gives a paragraph-long explanation of it, but I am not able to follow it, nor do I have any good intuition for why this process works.

One can compute a greatest common divisor easily by repeated division with remainder. For example, if $a = 314$ and $b = 136$, then 
  $$314 = 2 \cdot 136 + 42, \; 136 = 3 \cdot 42 + 10, \; 42 = 4 \cdot 10 + 2.$$
  Using the first of these equations, one can show that any integer combination of $314$ and $136$ can also be written as an integer combination of $136$ and the remainder $42$, and vice versa. So $\mathbb{Z}(314) + \mathbb{Z}(136) = \mathbb{Z}(136) + \mathbb{Z}(42)$, and therefore $\gcd(314, 136) = \gcd(136, 42)$. Similarly, $\gcd(136, 52) = \gcd(42,10) = \gcd(10,2) = 2$. So the greatest common divisor of $314$ and $136$ is $2$. This iterative method of finding the greatest common divisor of two integers is called the Euclidean Algorithm. 

I'm fine with the first line. If I have an integer combination
$$314x + 136y,$$
I can use the first given equation to write instead
$$314x + 136y = (2 \cdot 136 + 42)x + 136y = 2x \cdot 136 + 42x + 136y = (2x+y) \cdot 136 + 42x.$$
I can then write $136$ in terms of $42$ and $10$ and get a linear combination of $42$ and $10$, and so forth, and since the integers are closed, my coefficients will always be integers, so I end up with another integer combination. 
I cannot understand anything beyond this point in the text, though. I do not know what Artin means by the notation $\mathbb{Z}(314)$. Further, I have no intuition for why the $\gcd$ remains constant all the way down the chain or, even, why the last remaining, non-zero remainder in the algorithm is the $\gcd$. 
Any help with the intuition would be greatly appreciated.
 A: Start with vectors $A_0:=(a,1,0)$, $B_0:=(b,0,1)$. 
We want to find the $\gcd$ of the first component.
Certainly, the gcd doe not change if we swap $A$ and $B$ or subtract and integer multiple of one vector from the other.
Hence if we performm 

Given $A_n=(a_n,c_n,y_n)$ and $B_n=(b_n,u_nv_n)$ with $a_n\ge 0$ and $b_n>0$, let $q=\lfloor \frac {a_n}{b_n}\rfloor $ and then $A_{n+1}=B_n$, $B_{n+1}=A_n-qB_n$

then we have $\gcd(a_{n+1},b_{n+1})=\gcd(a_n,b_n\}=\ldots =\gcd(a,b)$. Also, $0\le b_{n+1}<b_n$ so that after finitely many steps we reach $v_n=0$, i.e., 
$$A_n=(d,x,y), B_n=(0,u,v) $$ 
where
$$d=\gcd(d,0)=\ldots=\gcd(a,b) $$
and from the book-keeping extra coordinates, we read off that
$$A_n=xA_0+yB_0,\quad B_n=uA_0+vB_0,$$
in particular,
$$ \gcd(a,b)=xa+yb.$$
A: Consider the $GCD(9,30)$.  Make a grid of width $9$ cells and height $30$ cells.

Now fill in squares of dimension $9 \times 9$, starting at the bottom.  If they fill the entire grid, then $9$ divides the larger number, and is the GCD.  For instance, if we were interested in $GCD(9, 27)$ then the $9 \times 9$ squares would fill the array and $9$ would (of course) be the $GCD(9,27)$.
But in our case they do not.  There is a $9 \times 3$ strip (white) across the top--the remainder.  Thus $GCD(9,30) \neq 9$.  
Consider that strip.  It is of height $3$.
So the Euclid algorithm says (in effect) "try tiling the white band with $3 \times 3$ squares."  Can we do that?  YES!  Thus $3$ divides the "white remainder" as well as the width $9$ of the earlier squares.  Thus $3$ divides both $9$ as well as $30$.  Why?  It divides the white band ($3$) and each big square ($9$); thus it divides $30$.  (In other words, $3$ divides $3$, it divides $9$, and thus it divides any multiple of $9$... thus it divides their sum:  $3 + 9 + 9 + 9 = 30$.)
Thus $GCD(9,30) = 3$.
If the $3$ happened not to divide the top (white) band, then there would be a remainder (column).  Iterate the procedure to find a new (smaller) value that tiles that remainder column, which then tiles the white band, which then also tiles the larger number.
Try it yourself!
Use this figure to find the $GCD(8, 22)$:

Answer

Do you see how $GCD(8,22)=2$?
Just for fun I illustrated the problem posed by the OP.  (I rotated the figure $90^\circ$ so it would fit here.)  It is hard to see, but the white remainder column is of dimensions $10 \times 2$, so indeed $GCD(136,314) = 2$.   

Pretty cool, huh?!
