Extended Euclidean Algorithm

The extended Euclidean algorithm is an algorithm to compute integers xx and yy such that

given  and .

The existence of such integers is guaranteed by Bézout’s Identity.

The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.

By reversing the steps in the Euclidean Algorithm, it is possible to find these integers  and . The whole idea is to start with the and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers.

Let’s find

We start with our GCD. We rewrite it in terms of the previous two terms:

We replace for  by taking our previous line  and writing it in terms of :

Collect like terms, the ’s, and we have

Repeat the process:

The final result is our answer:

Thus  and .