Euclidean algorithm and Bézout identity

Statement

Use the Euclidean algorithm to compute $\gcd(1071, 462)$, then express it as a linear combination of $1071$ and $462$.

Solution

Apply successive divisions: $1071 = 2 \cdot 462 + 147,$ $462 = 3 \cdot 147 + 21,$ $147 = 7 \cdot 21 + 0.$ The last nonzero remainder is $\boxed{21}$, so $\gcd(1071,462) = 21$.

Back-substituting (Bézout identity): $21 = 462 - 3 \cdot 147 = 462 - 3\,(1071 - 2\cdot 462) = 7 \cdot 462 - 3 \cdot 1071.$ Check: $7 \cdot 462 - 3 \cdot 1071 = 3234 - 3213 = 21$. Hence $21 = (-3)\cdot 1071 + 7 \cdot 462$.