Bézout identity and the Euclidean algorithm for polynomials over a field

If necessary interchange $f$ and $g$ so the second input is nonzero. Repeatedly apply [L2]; this also covers a zero first input, when the first remainder is already zero. Each nonzero remainder has strictly smaller natural degree than its divisor, so the process terminates. Every remainder is a polynomial linear combination of the original $f,g$ by back-substitution, and the last nonzero remainder $r$ divides the preceding remainder and hence, successively, both inputs.

Every common divisor of $f,g$ divides each remainder and therefore divides $r$; after multiplying $r$ and its back-substituted coefficients by $\operatorname{lc}(r)^{-1}$, the resulting monic polynomial $d=Af+Bg$ has the divisibility property and generates $(f,g)$, so [L1] identifies it with $\gcd(f,g)$.