# 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

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FvURxlr01QnBK1EVSPRzE%2Fa.png?alt=media&#x26;token=96208a0c-16fb-4b08-baac-0210c13415c6" alt=""><figcaption></figcaption></figure>
