Extended Euclidean algorithm

Summary

The extended Euclidean algorithm computes the greatest common divisor $d$ of two integers $a$ and $b$, and also integers $x$ and $y$ such that $a x + b y = d$. It does the steps of the Euclidean algorithm. At each step, it writes the new remainder as an integer combination of $a$ and $b$.