Extended Euclidean Algorithm

Extended Euclidean Algorithm is an extension of the Euclidean Algorithm which, as well as finding the greatest common divisor of two integers $a$ and $b$, also finds integers $x$ and $y$ such that:

$ax + by = \gcd(a, b)$

This is known as Bézout's identity.

It's commonly used to find the modular multiplicative inverse of a number (see Modular Arithmetic), which is a key step in generating keys for RSA.