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

Definition

Polynomial divisibility

For $f(x),g(x)\in \mathbb R[x]$, we say that $g(x)$ divides $f(x)$, written $g(x)\mid f(x)$, if there exists $q(x)\in \mathbb R[x]$ such that

$$f(x)=g(x)q(x).$$

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

Theorem

Mutual divisibility

For nonzero $f(x),g(x)\in \mathbb R[x]$,

$$g\mid f\text{ and }f\mid g \quad\Longleftrightarrow\quad f(x)=kg(x)$$

for some nonzero constant $k\in \mathbb R$.

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]

Definition

Greatest common divisor of polynomials

Let $f(x),g(x)\in \mathbb R[x]$ not both be zero. A polynomial $d(x)$ is a greatest common divisor of $f$ and $g$ if

1. $d(x)\mid f(x)$ and $d(x)\mid g(x)$;
2. every common divisor of $f$ and $g$ divides $d(x)$.

The notation $\gcd(f,g)$ means the unique monic greatest common divisor.

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.

Nonzero polynomials differing by a nonzero scalar are called associates. Nonzero constants are the units of a polynomial ring over a field: they have polynomial inverses. Conversely, if a product is $1$, additivity of degree forces both factors to have degree zero. This explains why nonzero scalar factors are ignored in divisibility.

If $d_1,d_2$ both satisfy the gcd definition, each divides the other, so $d_1=kd_2$ for a nonzero constant $k$. If both are monic, comparison of leading coefficients gives $k=1$. Any nonzero gcd becomes monic by division by its leading coefficient. This proves uniqueness of the normalized answer; existence will come from the Euclidean algorithm.

If $h\ne0$ has leading coefficient $\lambda$, then $\gcd(h,0)=\gcd(0,h)=h/\lambda$: every polynomial divides zero, so the common divisors are exactly the divisors of $h$. The pair $(0,0)$ is excluded from our monic-gcd definition. No monic polynomial can absorb all its common divisors, since these include polynomials of arbitrarily large degree.

Common mistake

A gcd is monic by convention

If a Euclidean computation ends with $-2x+2$, the gcd is not usually recorded as $-2x+2$. Since $-2x+2=-2(x-1)$, the monic gcd is $x-1$.

The Euclidean algorithm for polynomials

Proof: What the Euclidean algorithm preserves and normalizes

Starting conditions. Work with $f,g\in\mathbb R[x]$, not both zero. Handle a zero input by the convention above; otherwise divide by a nonzero polynomial. Each division has remainder zero or remainder degree strictly below the divisor's degree. No degree of the zero polynomial is needed.

Invariant. The equations $r=f-qg$ and $f=qg+r$ prove both directions: a polynomial divides $f,g$ exactly when it divides $g,r$. Thus each step preserves the whole collection of common divisors, not merely their degrees.

Termination and target. Nonzero remainder degrees form a strictly decreasing sequence of nonnegative integers. It cannot continue forever. At the final pair $(h,0)$, every original common divisor divides $h$, while $h$ itself divides both original inputs by the invariant. Hence $h$ is a gcd.

Normalization. If $\lambda$ is the leading coefficient of $h$, return $h/\lambda$. This scaling preserves divisibility and makes the answer monic. In the example below, $h=-x+1$ and $\lambda=-1$, so the result is $x-1$. Any Bezout coefficients for $h$ must also be divided by $\lambda$; changing only the left side would invalidate the identity.

Worked example

A polynomial Euclidean algorithm

Let

$$f(x)=4x^4-2x^3-16x^2+5x+9,\qquad g(x)=2x^3-x^2-5x+4.$$

Successive divisions give

$$f(x)=(2x)g(x)+(-6x^2-3x+9),$$$$g(x)=\left(-\frac13x+\frac13\right)(-6x^2-3x+9)+(-x+1),$$

and

$$-6x^2-3x+9=(6x+9)(-x+1)+0.$$

The last nonzero remainder is $-x+1$, so the monic gcd is

$$\gcd(f,g)=x-1.$$

Bezout identities

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

Theorem

Polynomial Bezout identity

If $f(x),g(x)\in \mathbb R[x]$ are nonzero, then there exist $a(x),b(x)\in \mathbb R[x]$ such that

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

To prove existence, start with $f=1f+0g$ and $g=0f+1g$. If two successive remainders have expressions $r_i=A_if+B_ig$, the next division gives

$$r_{i+1}=r_{i-1}-q_i r_i =(A_{i-1}-q_iA_i)f+(B_{i-1}-q_iB_i)g.$$

Thus every remainder has polynomial coefficients in a linear combination of $f,g$. At termination, divide the final coefficients by the leading coefficient of the final nonzero remainder. This yields the monic gcd, proving Bezout's identity. If one input is zero, the formula still holds: for $f\ne0$ with leading coefficient $\lambda$, use coefficients $1/\lambda,0$ for $(f,0)$, and interchange them for $(0,f)$.

For the example, set $r_1=-6x^2-3x+9$ and $q_2=-x/3+1/3$. The recorded second division gives $-x+1=g-q_2r_1$. Negate first, then substitute $r_1=f-2xg$:

$$x-1=q_2r_1-g=q_2(f-2xg)-g=q_2f+(-2xq_2-1)g.$$

Consequently the explicit normalized identity is

$$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.

A Bezout pair is not unique. If $Af+Bg=d=\gcd(f,g)$, then for any $t\in\mathbb R[x]$ in the same coefficient field,

$$\left(A+t\frac gd\right)f+\left(B-t\frac fd\right)g=d.$$

Both quotients are polynomials because $d$ divides $f,g$; the two added terms cancel. Normalizing the gcd fixes its value, not a unique pair of coefficients.

Definition

Relatively prime polynomials

Nonzero polynomials $f(x)$ and $g(x)$ are relatively prime if

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

Equivalently, there exist $a(x),b(x)\in \mathbb R[x]$ such that

$$a(x)f(x)+b(x)g(x)=1.$$

Irreducible polynomials

Definition

Irreducible over a field

Let $F$ be a field. A nonconstant polynomial $p(x)\in F[x]$ is irreducible over $F$ if it cannot be written as

$$p(x)=g(x)h(x)$$

with $g(x),h(x)\in F[x]$ and

$$0\lt\deg g,\deg h\lt\deg p.$$

Irreducibility depends on the coefficient field.

Worked example

Changing the field can change irreducibility

The polynomial $x^2-2$ is irreducible over $\mathbb Q$, but reducible over $\mathbb R$:

$$x^2-2=(x-\sqrt2)(x+\sqrt2).$$

The polynomial $x^2+1$ is irreducible over $\mathbb R$, but reducible over $\mathbb C$:

$$x^2+1=(x-i)(x+i).$$

Counterexample mode

No root in one field is not irreducibility in every field

The claim that irreducibility is unchanged when coefficients are enlarged is false. In the preceding examples, $\sqrt2\notin\mathbb Q$ but $\sqrt2\in\mathbb R$, and $i\notin\mathbb R$ but $i\in\mathbb C$; the new coefficients make the displayed linear factors available.

The correct test for a quadratic over a field $F$ is that it is irreducible if and only if it has no root in $F$. A nontrivial factorization must have degrees $1+1$, and a linear factor gives a root; conversely, a root gives a linear factor by the factor theorem. Thus $x^2-2$ has no rational root, while $x^2+1$ has no real root because $t^2+1\gt0$ for real $t$. The test's degree-two hypothesis matters; this argument does not establish a no-root criterion for arbitrary degrees.

Over $\mathbb C$, every irreducible polynomial is linear, because the fundamental theorem of algebra gives a root for every nonconstant polynomial. Over $\mathbb 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 \mathbb R$, then

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

has real coefficients and no real linear factor.

For a real polynomial, nonreal roots occur with their conjugates. Pairing them gives these real quadratic factors; real roots give linear factors. A polynomial of higher degree therefore has a proper real factor. Conversely, linear polynomials are irreducible by degree, and a real quadratic with negative discriminant has no real root, so it is irreducible by the quadratic test. In the quadratic statement $a\ne0$ is understood.

Divisibility and factorization proofs

The following arguments work over a field $F$, including $\mathbb Q$, $\mathbb R$, and $\mathbb C$: polynomial division requires division by a nonzero leading coefficient, which is available in every field. The preceding gcd and Bezout proofs therefore apply in $F[x]$ as well.

Theorem

An irreducible polynomial divides a product as a prime does

Let $F$ be a field, let $p\in F[x]$ be irreducible, and let $a,b\in F[x]$. If $p\nmid a$, then $\gcd(a,p)=1$. If $p\mid ab$, then $p\mid a$ or $p\mid b$.

Put $d=\gcd(a,p)$. Since $d\mid p$, write $p=de$. Irreducibility forces $d$ or $e$ to be constant. If $e$ is constant, it is nonzero and $d$ is an associate of $p$; then $d\mid a$ forces $p\mid a$. When $p\nmid a$, this is impossible, so $d$ is constant, and its monic normalization is $1$.

Now suppose $p\mid ab$. If $p\mid a$, the desired conclusion already holds. Otherwise Bezout gives $ua+vp=1$. Multiplication by $b$ yields $b=uab+vpb$. Both terms on the right are divisible by $p$, so $p\mid b$. This proves the prime property rather than assuming it in the definition of irreducibility.

Theorem

Solvability of a polynomial linear combination

Let $F$ be a field and $a,b,c\in F[x]$, with $a,b$ not both zero. Put $d=\gcd(a,b)$. There exist $u,v\in F[x]$ satisfying $au+bv=c$ if and only if $d\mid c$.

For necessity, $d\mid a,b$ implies $d\mid au+bv$, so any solution forces $d\mid c$. For sufficiency, if $c=dh$, choose Bezout coefficients $A,B$ with $Aa+Bb=d$. Multiplying by $h$ gives a solution $u=hA$, $v=hB$. This constructs a solution for every divisible right-hand side, rather than only ruling out impossible ones. If $a=b=0$, treat the equation separately: it is solvable exactly when $c=0$, independently of a gcd convention.

Theorem

Existence and uniqueness of irreducible factorization

Let $F$ be a field and $f\in F[x]$ be nonconstant. Then $f=c\,p_1\cdots p_r$, where $c\in F$ is nonzero and each $p_j$ is monic and irreducible. The scalar $c$ and the multiset of monic factors are unique; factors may be repeated, and their order is irrelevant.

Existence. Use induction on the positive degree of $f$. Degree-one polynomials are irreducible. If $f$ is already irreducible, normalize it and keep its leading coefficient as the scalar. Otherwise $f=gh$ with both factors of positive degree strictly below $\deg f$. Induction factors $g$ and $h$ into irreducibles, so multiplying gives a factorization of $f$. Normalizing every factor collects all nonzero scalar factors into $c$. Strict degree decrease supplies termination; repeated factors are allowed.

Uniqueness. Suppose $c\,p_1\cdots p_r=d\,q_1\cdots q_s$ are two such factorizations. The prime property applied repeatedly shows that $p_1$ divides some $q_j$: it cannot divide the nonzero constant $d$, since it has positive degree. Irreducibility of $q_j$ makes the quotient constant, and monicity forces $p_1=q_j$. Reorder and cancel this common nonzero factor; cancellation is valid because a polynomial ring over a field has no zero divisors. Repeat. If one list ended before the other, a nonzero constant would equal a positive-degree product, impossible by degree. Hence the lists match, including multiplicities, and the remaining equality is $c=d$.

Follow the polynomial Euclidean algorithm produce a monic gcd, reverse into a Bezout identity, and support field-dependent irreducibility tests.

1. Monic gcd

   Scalar multiples such as x-1, 5x-5, and -2x+2 have the same divisibility behavior, so gcds are recorded using the monic representative.

2. Euclidean invariant

   From f=gq+r, the common divisors of f and g are exactly the common divisors of g and r; hence gcd(f,g)=gcd(g,r).

3. Example chain

   For the chapter example, the remainders are r1=-6x^2-3x+9, r2=-x+1, and then 0.

4. Back-substitution

   The last nonzero remainder -x+1 is normalized to x-1, then reversed into x-1=(-1/3x+1/3)f+(2/3x^2-2/3x-1)g.

5. Field dependence

   Irreducibility depends on the field: x^2-2 changes between Q and R, while x^2+1 changes between R and C.

6. Prime-like role

   If p is irreducible and p does not divide a, Bezout gives ua+vp=1; multiplying by b explains why p|ab forces p|b.

Polynomial gcd work has three linked layers: normalize associates to a monic gcd, preserve common divisors through the Euclidean remainder chain, and use Bezout to prove irreducible-polynomial divisibility tests.

Worked example: the solvability criterion

Worked example

Use gcd to decide a polynomial equation

Determine whether there exist $u(x),v(x)\in \mathbb R[x]$ such that

$$(x^2-1)u(x)+(x-1)v(x)=x+1.$$

The left side is a polynomial combination of $x^2-1$ and $x-1$. Since

$$x^2-1=(x-1)(x+1),$$

we have

$$\gcd(x^2-1,x-1)=x-1.$$

By the polynomial Bezout-solvability criterion, the equation has a solution only if $x-1$ divides $x+1$. It does not, because substituting $x=1$ gives $2\ne0$. Therefore no such polynomials $u$ and $v$ exist.

Common mistakes

Common mistake

Treating scalar multiples as different gcd answers

In $\mathbb R[x]$, $x-1$, $2x-2$, and $-7x+7$ have the same divisibility content. Only $x-1$ is the monic representative, so it is the standard value of the gcd.

Common mistake

Saying irreducible without naming the field

The phrase "$x^2-2$ is irreducible" is incomplete. It is irreducible over $\mathbb Q$, but reducible over $\mathbb R$. Always state the coefficient field when irreducibility is the issue.

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 $\mathbb C$ only linear polynomials are irreducible, while over $\mathbb R$ irreducibles are linear polynomials and quadratics with negative discriminant.

Study guide for the exercises

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 $\mathbb R$; a quadratic with no real root will factor over $\mathbb C$. Over $\mathbb R$, the discriminant test is enough for quadratics. Over $\mathbb Q$, rational-root and number-system information matters. For example, $x^2-5$ is irreducible over $\mathbb Q$ because $\sqrt5$ is not rational, but it is reducible over $\mathbb R$.

Quick checks

Checkpoint

Why do we choose the monic gcd in $\mathbb R[x]$?

Think about multiplying a common divisor by a nonzero constant.

Solution · Answer

Greatest common divisors are unique only up to a nonzero constant factor, so choosing the monic representative makes the notation unique.

Checkpoint

What is the monic gcd of $-x+1$ and $0$?

Normalize the nonzero polynomial.

Solution · Answer

The gcd is $x-1$, because $-x+1=-(x-1)$ and the monic representative is $x-1$.

Checkpoint

Is $x^2+1$ irreducible over $\mathbb R$? Is it irreducible over $\mathbb C$?

Use the available roots in each field.

Solution · Answer

It is irreducible over $\mathbb R$ because it has no real root, but it is reducible over $\mathbb C$ since $x^2+1=(x-i)(x+i)$.

Exercises

In Exercises 4 and 5, fix a field $F$; all polynomials belong to $F[x]$, and irreducibility is over $F$.

1. Use the Euclidean algorithm to compute $\gcd(x^3-1,x^2-1)$ in $\mathbb 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 $\mathbb Q$, $\mathbb R$, and $\mathbb 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 \mathbb R[x]$ such that $(x^2-1)u(x)+(x-1)v(x)=x+1$.

Solution · Model solution 1

Divide $x^3-1=x(x^2-1)+(x-1)$, then $x^2-1=(x+1)(x-1)+0$. The last nonzero remainder $x-1$ is already monic, so it is the gcd.

Solution · Model solution 2

Write $A=-x/3+1/3$ and $B=2x^2/3-2x/3-1$. Expanding the two products gives

$$Af=-\frac43x^5+2x^4+\frac{14}{3}x^3-7x^2-\frac43x+3,$$$$Bg=\frac43x^5-2x^4-\frac{14}{3}x^3+7x^2+\frac73x-4.$$

The coefficients of $x^5,x^4,x^3,x^2$ cancel in pairs. The remaining terms give

$$Af+Bg=\left(-\frac43+\frac73\right)x+(3-4)=x-1.$$

The last nonzero remainder was $-x+1$. Making it monic divides both the remainder and its two Bezout coefficients by $-1$; the $A,B$ used here already include that normalization.

Solution · Model solution 3

$x^2-5$ is irreducible over $\mathbb Q$ because $\sqrt5\notin \mathbb Q$; reducible over $\mathbb R$ as $(x-\sqrt5)(x+\sqrt5)$; and therefore reducible over $\mathbb C$.

Solution · Model solution 4

Since $p$ is irreducible, its only divisors up to constants are $1$ and $p$. If $p\nmid a$, the gcd cannot have degree $\deg p$, so it must be $1$.

Solution · Model solution 5

From part 4, if $p\nmid a$, then $\gcd(a,p)=1$. Choose $u,v$ with $ua+vp=1$. Multiplying by $b$ gives $uab+vpb=b$; both terms on the left are divisible by $p$, so $p\mid b$.

Solution · Model solution 6

The gcd of $x^2-1$ and $x-1$ is $x-1$. Since $x-1$ does not divide $x+1$, no such $u,v$ exist.