The Extended Euclidean Algorithm

Finds integers x and y with ax + by = the greatest common divisor. Running the Euclidean algorithm while also tracking how many of a and of b each remainder holds leaves x and y behind once the division comes out even. This is the basis for solving linear Diophantine equations.

For two whole numbers $a$ and $b$ , this finds whole numbers $x$ and $y$ satisfying the following.

ax + by = \gcd(a, b)

That such $x$ and $y$ always exist is known as Bezout's identity. The ordinary Euclidean algorithm returns only the greatest common divisor, but tracking how many of $a$ and of $b$ each remainder holds leaves $x$ and $y$ behind once the division comes out even.

Example

Take $a = 240$ and $b = 46$ . The greatest common divisor is 2, with $x = -9$ and $y = 47$ . Checking, $240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2$ .

Where it is used

A linear Diophantine equation $ax + by = c$ has whole-number solutions only when $c$ is a multiple of the greatest common divisor. This calculation finds one such solution to start from.

It also finds $x$ with $ax \equiv 1 \pmod{m}$ , the inverse modulo $m$ . When $a$ and $m$ share no factor, $ax + my = 1$ can be solved and that $x$ is the answer. Cryptography relies on this.

Notes

The pair $x$ , $y$ is not unique. Adding $\dfrac{b}{\gcd(a, b)}$ to $x$ and subtracting $\dfrac{a}{\gcd(a, b)}$ from $y$ keeps the identity true. The pair the algorithm returns is the one given here.