> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-mcs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/the-extended-euclids-algorithm.md).

# 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&amp;token=96208a0c-16fb-4b08-baac-0210c13415c6" alt=""><figcaption></figcaption></figure>