How do the Euclidean and extended Euclidean algorithms work?

Question

One can use the extended Euclidean algorithm to calculate the modular multiplicative inverse of a number, as it will be in the form $a x + b y = 1$, and if you take mod $b$ of both sides you get the inverse of $a$ in mod $b$. However, why does the Euclidean algorithm work? Specifically, why is the last non-zero remainder gcd(a,b)? And how come you can just substitute everything back and it magically give you gcd(a,b) in terms of integers? Thanks so much.

Answer 1

That is because it relies on the following easy lemma:

The set of common divisors of $a$ and $b$ is the same as the set of common divisors of $b$ and $b\bmod a$. Hence $\gcd(a,b)=\gcd(b, b\bmod a)$.

The extended Euclidean algorithm relies on a more precise analysis of the successive divisions: if we denote by $r_0=a$, $r_1=b$, $r_2=r_0\bmod r_1$, … , $r_{n+1}=r_n\bmod r_{n-1}$, … , the $n$-th division equality: $$r_{n-1}=q_nr_n+r_{n+1}$$ can be rewritten as $$r_{n+1}=r_{n-1}-q_nr_n.$$ An easy induction shows that, not only the last non-zero remainder satisfies a Bézout's identity, but that all intermediate remainders satisfy such an identity: $$r_n=u_n a+v_nb.$$ The sequences of coefficients $(u_n)$ and $(v_n)$ are initialised as $$u_0=1,~v_0=0,\qquad u_1=0,~v_1=0,$$ and they satisfy the same recurrence relation as the remainders: $$u_{n+1}=u_{n-1}-q_nu_n, \qquad v_{n+1}=v_{n-1}-q_nv_n.$$