Proof: there exist $x,y\in \mathbb Z$ such that $xa+yb=\gcd (a,b)$

Question

Let $a,b\in\mathbb Z$ and $d=\gcd(a,b)$. Then there exist $x,y\in\mathbb Z$ such that $xa+yb=d$.

I don't really understand the proof for this theorem.

They state the following (translation):

We are going to construct two sequences of integers $x_0,x_1,x_2,\dots$ and $y_0,y_1,y_2,\dots$ such that $$ x_na+y_nb=r_n. $$ For $n=0$ we have $r_n=|a|=\pm a$, so we can take $x_0=\pm 1$ and $y_0=0$. In the same way we can take $x_1=0$ and $y_1=\pm 1$. If $n\geq1$, and $r_n\neq0$, then we can determine $x_{n+1}$ and $y_{n+1}$ by subtraction $q_n$ times $$ x_na+y_nb=r_n $$ from $$ x_{n-1}a+y_{n-1}b=r_{n-1}. $$ Because $r_{n-1}-q_nr_n=r_{n+1}$, this gives $$ (x_{n-1}-q_nx_n)\cdot a+(y_{n-1}-q_ny_n)\cdot b=r_{n+1}, $$ so we can choose $x_{n+1}=x_{n-1}-q_nx_n$ and $y_{n+1}=y_{n-1}-q_ny_n$. Continuing this way, we will eventually get $r_m=0$, and then we have $$ x_{m-1}a+y_{m-1}b=r_{m-1}=d. $$

I have two questions concerning this proof:

1) Do we need that $|a|\geq|b|$?

2) How do we determine $q_n$?

3) And why is the last line true; $$ x_{m-1}a+y_{m-1}b=r_{m-1}=d. $$

Answer 1

Here are some answers, hope they help:

Starting with

2. Given $r_{n-1}$ and $r_n$, we find $r_{n+1}$ by Euclidean division: we divide $r_{n-1}$ by $r_n$, writing uniquely $$r_{n-1} = q r_n + r, \ \ \ \ \ \ \ \ \ 0\leq r < r_n$$ We then set $q_n = q$ and $r_{n+1}= r$. So $q_n$ is just determined by division with remainder.

Now

1. Given the answer to 2), no you do not need to take $|a| \geq |b|$. For example, if you took $a=3$ and $b=5$, this method would have $3,5,3,2,1,0$ as the sequence $(r_n)$. We just waste a step in the beginning. This illustrates the general pattern, if $r_0 < r_1$, we force $r_2 = r_0$ and then get back on track.

Finally

3. From the answer to 2), the sequence $(r_n)$ is generated by running the Euclidean algorithm on $|a|, |b|$. I assume that you've already encountered and understood the Euclidean algorithm.