Extended Euclidean algorithm

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$. When $a$ and $b$ are coprime, either coefficient gives the corresponding modular multiplicative inverse.