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$.

Remarks

The coefficients $x$ and $y$ prove Bézout's identity for $a$ and $b$. When $\gcd(a, n) = 1$, the coefficient $x$ of $a$ is a modular multiplicative inverse of $a$ modulo $n$.

Explanations

L1 human

For $a = 48$ and $b = 18$, the Euclidean algorithm gives $12 = 48 - 2 \cdot 18$ and $6 = 18 - 1 \cdot 12$. Put the first equation into the second: $6 = 18 - (48 - 2 \cdot 18) = 3 \cdot 18 - 1 \cdot 48$. So $x = -1$ and $y = 3$ give $48 x + 18 y = 6$.