The Euclidean algorithm and Bézout's identity for integers carry over to polynomials word for word, because division with remainder works the same way. The payoff is a method for inverting elements of $F[x]/(p(x))$, the arithmetic of the new fields we are about to build.
Definition. Over a field $F$, $\gcd(f, g)$ is the monic common divisor of largest degree (monic makes it unique; any nonzero constant multiple divides just as well).
💡 Why it works
Euclidean algorithm. Divide $f = q_{1}g + r_{1}$, then $g = q_{2}r_{1} + r_{2}$, and so on; degrees drop each time, so a remainder eventually is $0$. The common divisors of $f$ and $g$ are the same as those of $g$ and $r_{1}$ (since $r_{1} = f - q_{1}g$), so the last nonzero remainder, made monic, is the gcd. Running the equations backward writes $$\gcd(f, g) = a(x)f(x) + b(x)g(x).$$ Inverses. If $p$ is irreducible and $p \nmid g$, then $\gcd(g, p) = 1 = ag + bp$, so $ag \equiv 1$ modulo $p$: the class of $a$ is the inverse of $g$ in $F[x]/(p)$.
✏️ Worked example: A gcd in $\mathbb{Z}_{2}[x]$
Find $\gcd(x^{3} + 1, x^{2} + 1)$ in $\mathbb{Z}_{2}[x]$.
- $x^{3} + 1 = x(x^{2} + 1) + (x + 1)$, since $x(x^{2} + 1) = x^{3} + x$ and $x^{3} + 1 - x^{3} - x = x + 1$ (mod 2).
- $x^{2} + 1 = (x + 1)(x + 1) + 0$, since $(x + 1)^{2} = x^{2} + 2x + 1 = x^{2} + 1$.
- The last nonzero remainder is $x + 1$, already monic.
Answer: $x + 1$.
✏️ Worked example: Over $\mathbb{Q}$ by factoring
Find the monic gcd of $f = 2(x - 1)(x - 2)(x + 3)$ and $g = (x - 1)(x + 3)(x + 4)$ in $\mathbb{Q}[x]$.
- Common factors: $(x - 1)(x + 3) = x^{2} + 2x - 3$.
- The constant $2$ is a unit in $\mathbb{Q}$ and does not count.
Answer: $x^{2} + 2x - 3$.
✏️ Worked example: An inverse in a quotient ring
In $\mathbb{Z}_{2}[x]/(x^{3} + x + 1)$, find the inverse of $x$.
- Divide: $x^{3} + x + 1 = (x^{2} + 1)\,x + 1$.
- So $1 = (x^{3} + x + 1) - (x^{2} + 1)x$, and modulo $x^{3} + x + 1$ this says $(x^{2} + 1)x \equiv -1 = 1$.
- Check: $x(x^{2} + 1) = x^{3} + x$, and $x^{3} = x + 1$ here, so $x^{3} + x = 2x + 1 = 1$.
Answer: $x^{-1} = x^{2} + 1$.
One structural consequence: in $F[x]$ every ideal is generated by one polynomial (take a nonzero element of least degree and divide), just as every ideal of $\mathbb{Z}$ is $(n)$. Rings with this property are called principal ideal domains.
⚠️ Common mistake
Forgetting to make the gcd monic (over $\mathbb{Z}_{5}$, $3x + 1$ and $x + 2$ are the same gcd up to the unit $3$; the answer is the monic one, $x + 2$), or reporting the last remainder, $0$, instead of the one before it.
Why the gcd decides invertibility. Let $g \ne 0$ have degree less than $\deg p$. In $F[x]/(p)$, $g$ has an inverse exactly when $\gcd(g, p) = 1$. If $ag + bp = 1$, then $ag \equiv 1$. If instead $d = \gcd(g, p)$ has positive degree, then $g \cdot \frac{p}{d} = \frac{g}{d} \cdot p \equiv 0$ with $\frac{p}{d} \not\equiv 0$, so $g$ is a zero divisor and has no inverse.
🔑 Key idea
The Euclidean algorithm finds $\gcd(f, g)$ in $F[x]$ (made monic),
and running it backward gives $\gcd = af + bg$. When $\gcd(g, p) = 1$, the coefficient $a$ is the inverse of $g$ modulo $p$.