Working backwards

Theorem 22

Bézout

If $\gcd(a, b) = d$ , then $a\cdot x + b\cdot y = d$ for some integers $x$ , $y$ .

Run Euclid’s algorithm, then substitute the remainders back from the bottom up.

01 $12 = 2\cdot 5 + 2$ , so $2 = 12 - 2\cdot 5$ .Step $1$
02 $5 = 2\cdot 2 + 1$ , so $1 = 5 - 2\cdot 2$ .Step $2$
03Substitute: $1 = 5 - 2\cdot (12 - 2\cdot 5) = 5\cdot 5 - 2\cdot 12$ .Back-substitute
04So $\gcd(12, 5) = 1 = 12\cdot (-2) + 5\cdot 5$ .Conclusion