8.2 Polynomial gcds and irreducibility

From integer gcds to polynomial gcds

Chapter 7 showed that integer divisibility is controlled by gcds, the Euclidean algorithm, Bezout identities, and prime factorization. Chapter 8 repeats the same architecture for polynomials. The analogy is powerful, but there is one new subtlety: multiplying a polynomial by a nonzero constant does not change its divisibility behavior.

For example, $x-1$ and $5x-5$ divide exactly the same polynomials up to a constant factor. To make a gcd unique, we choose the monic representative.

Polynomial divisibility and associates

Two nonzero polynomials divide each other exactly when they differ by a nonzero constant factor.

The proof uses degrees. If $f=d_1g$ and $g=d_2f$, then $f=d_1d_2f$. Since $f\ne0$, the product $d_1d_2$ must be the constant polynomial 1, so both $d_1$ and $d_2$ are constant.

Greatest common divisors in R[x]

The second condition is often more useful than the word "greatest." There is no natural ordering by size for polynomials, so the gcd is characterized by divisibility: it is the common divisor that absorbs every other common divisor.

The Euclidean algorithm for polynomials

The division algorithm immediately gives the polynomial Euclidean algorithm. If

$$f(x)=g(x)q(x)+r(x),\qquad \deg r\lt\deg g,$$

then

$$\gcd(f,g)=\gcd(g,r).$$

Indeed, every common divisor of f and g divides $r=f-gq$, and every common divisor of g and r divides $f=gq+r$.

Repeating this step produces remainders of strictly decreasing degree, so the algorithm must stop. The last nonzero remainder, made monic, is the gcd.

Bezout identities

The extended Euclidean algorithm also survives in R[x].

For the worked example above, back-substitution gives

$$x-1= \left(-\frac13x+\frac13\right)f(x) \left(\frac23x^2-\frac23x-1\right)g(x).$$

This identity is more than a computational trick. It proves that if $\gcd(f,g)=1$, then polynomial combinations of f and g can produce the constant polynomial 1. That is the engine behind many divisibility theorems.

Irreducible polynomials

Irreducibility depends on the coefficient field.

Over $C$, every irreducible polynomial is linear, because the fundamental theorem of algebra gives a root for every nonconstant polynomial. Over $R$, the irreducible polynomials are exactly:

• linear polynomials;
• quadratic polynomials $ax^2+bx+c$ with discriminant $b^2-4ac\lt0$.

The quadratic case reflects complex conjugate roots. If $\alpha\notin R$, then

$$(x-\alpha)(x-\bar\alpha)=x^2-2\operatorname{Re}(\alpha)x+|\alpha|^2$$

has real coefficients and no real linear factor.

Divisibility principles for irreducibles

Irreducible polynomials behave like primes.

The proofs mirror the integer proofs from chapter 7. The Bezout identity gives the key step. For example, if p is irreducible and $p\nmid a$, then $\gcd(a,p)=1$, so

$$u(x)a(x)+v(x)p(x)=1.$$

Multiplying by b(x) shows that if $p\mid a(x)b(x)$, then $p\mid b(x)$.

Proof sketch or proof idea

The safest way to reason about polynomial gcds is to avoid thinking of a gcd as "the biggest expression." Polynomials do not come with a natural size order that behaves like the order on positive integers. Instead, the gcd is the common divisor that is divisible by every other common divisor. This is why the second clause in the definition is the real content.

The Euclidean step

$$\gcd(f,g)=\gcd(g,r)$$

is just a divisibility equivalence. If a polynomial divides both f and g, it divides $r=f-gq$. Conversely, if it divides both g and r, it divides $f=gq+r$. Thus the two pairs have exactly the same common divisors, and hence the same monic gcd. The only algorithmic ingredient is that $\deg r\lt\deg g$, so the sequence of degrees strictly decreases.

Bezout's identity is obtained by keeping the quotient equations instead of throwing them away. Each remainder is a polynomial combination of the two previous remainders. Since the first two remainders are f and g, every later remainder is a polynomial combination of f and g. The final nonzero remainder is a constant multiple of the gcd, and after making it monic we get

$$\gcd(f,g)=a(x)f(x)+b(x)g(x).$$

This proof also explains why Bezout identities are not unique. Once one pair a,b works, other pairs may be obtained by adding and subtracting suitable multiples of $g/\gcd(f,g)$ and $f/\gcd(f,g)$. In checkpoint problems, a prompt must either ask for a specific Euclidean back-substitution pair or check the identity itself.

Common mistakes

Summary

Polynomial gcd theory copies the structure of integer gcd theory, with degree replacing size and monic normalization replacing positivity. The Euclidean algorithm computes a gcd by preserving common divisors while lowering degree. The extended algorithm gives Bezout identities. Irreducible polynomials play the role of primes, but irreducibility depends on the field: over $C$ only linear polynomials are irreducible, while over $R$ irreducibles are linear polynomials and quadratics with negative discriminant.

Study guide for the exercises

When a problem asks for a polynomial gcd, decide first whether factoring is obvious. If both polynomials factor cleanly, the common monic factors can be read directly. If not, use the Euclidean algorithm exactly as with integers: divide, replace the pair by divisor and remainder, and repeat until the remainder is zero. The last nonzero remainder may need to be multiplied by a nonzero constant to make it monic.

When a problem asks for a Bezout identity, keep a record of each division equation. The gcd is found by running the Euclidean algorithm downward, but the Bezout expression is found by running the equations backward. Students often make errors by changing a remainder without updating the earlier equation it came from. A useful check is to expand the final $a(x)f(x)+b(x)g(x)$ and verify that every higher-degree term cancels.

For irreducibility questions, the coefficient field is part of the problem. A quadratic with no rational root may still factor over $R$; a quadratic with no real root will factor over $C$. Over $R$, the discriminant test is enough for quadratics. Over $Q$, rational-root and number-system information matters. For example, $x^2-5$ is irreducible over $Q$ because $\sqrt5$ is not rational, but it is reducible over $R$.

For proof questions, reuse the integer chapter deliberately. The statement "irreducible divides a product implies it divides a factor" is not magic; it is Bézout plus multiplication. If $p\nmid a$, then $\gcd(a,p)=1$, so $ua+vp=1$. Multiplying by b turns this identity into a divisibility proof for b whenever p divides ab.

Quick checks

Exercises

1. Use the Euclidean algorithm to compute $\gcd(x^3-1,x^2-1)$ in R[x].
2. In the worked example, verify the Bezout identity for $x-1$ by expanding the right-hand side.
3. Decide whether $x^2-5$ is irreducible over $Q$, $R$, and $C$.
4. Prove: if p(x) is irreducible and $p\nmid a(x)$, then $\gcd(a,p)=1$.
5. Prove: if p(x) is irreducible and $p\mid a(x)b(x)$, then $p\mid a(x)$ or $p\mid b(x)$.
6. Determine whether there exist $u(x),v(x)\in R[x]$ such that $(x^2-1)u(x)+(x-1)v(x)=x+1$.