Extended Euclidean Algorithm: why does it work?

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?!

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.$$