The Extended Euclid's Algorithm

Euclid's algorithm starts a sequence with $a$ and $b$ and proceeds by doing modular reductions on consecutive terms of the sequence until zero in reached.

Let the sequence begin with $x_0 = a$ and $x_1 = b$. At any time, let $x_k = s_ka + t_kb$. So, $s_0 = t_1 = 1$, and $s_1 = t_0 = 0$.

The next term of the sequence is given by $x_k = x_{k-2} mod x_{k-1}$. Let $q_k = \lfloor \frac{x_{k-2}}{x_{k-1}} \rfloor$.

Then, $x_k = x_{k-2} - q_kx_{k-1}$, $s_k = s_{k-2} - q_ks_{k-1}$, and $t_k = t_{k-2} - q_kt_{k-1}$.

We have to stop wjem $x_k = 0$, at which time $gcd(a,b) = x_{k-1}$. But here we know more: $x_{k-1} = s_{k-1}a + t_{k-1}b$.

If $gcd(a,b) = 1$ then $x_{k-1} = 1$, and this formula allows us to compute easily.

• $a^{-1} mod b = s_{k-1} mod b$ and

• $b^{-1}mod a = t_{k-1} mod a$

Example