Double-checking work on finding gcd with Euclidean algorithm

Question

I'm still learning the Euclidean algorithm and am hoping that someone can check my work on this problem:

Find $gcd(1001, 11)$

$1001 = 91(11) + 0 = 90(11) + 11$

$gcd(1001, 11) = 11$

Answer 1

As soon as you have $1001 = 91 \times 11 + 0$, you know that 11 is a common divisor of both 11 and 1001, and since it is the greatest possible divisor of 11, it is the greatest common divisor of the two.

In general, when performing the Euclidean algorithm on $x$ and $y$ taking $x_i = q_i y_i + d_i$, as soon as $d_i = 0$ then $y_i$ is the GCD.

Answer 2

Suppose $d|a$ and $d|b$. Then $d|ma+nb$. In other words, any common factor of $a$ and $b$ is also a common factor of the sum of any products of $a$ and $b$.

Further, If $d|x$, then $gcd(d,x)=d$.

This is the basis of the Euclidean Algorithm.

WLOG b<a.

Then $a=qb+r$ for some positive values of q, r, where $0\le r<b$. $r$ is not allowed to be $b$ because then you can just add 1 to q and let $r=0$. $qb$ is the largest multiple of $b$ that is less than $a$.

If $d|a$ and $d|b$ then d|r by the above and we have that $r<b$.

On the next step, we have $b=q_2r+r_2$. Again if $d|b$ and $d|r$, then $d|r_2$, $r_2<r$.

So we are guaranteed ever decreasing remainders. The only common factor between 1 and any other integer is 1. So if the remainder is ever 1, then we know the gcd of the two original numbers is 1.

Suppose the remainder is 0. Then we have some x=qy+0. Well, y divides y and by that expression it also divides x. So that must be their gcd.