Polynomial Greatest Common Divisor¶

Definition¶

A greatest common divisor (GCD) of two polynomials $a(x)$ and $b(x)$, not both zero, is a polynomial of greatest possible degree that divides both $a(x)$ and $b(x)$.

Interpretation¶

A greatest common divisor of $a(x)$ and $b(x)$ is a common factor that is as large as possible, with size measured by degree, just as the GCD of two integers is the largest integer that divides both.

The polynomial GCD can be found with the Euclidean algorithm. Polynomial long division gives $a=qb+r$ with $r=0$ or $\deg r<\deg b$$\mathrm{deg}b$. Every common divisor of $a$ and $b$ divides $r=a-qb$$qb$, and every common divisor of $b$ and $r$ divides $a=qb+r$$r$, so the pairs $(a,b)$ and $(b,r)$ have the same common divisors. The algorithm keeps replacing the pair by divisor and remainder. The degrees of the remainders strictly decrease, so the remainder eventually becomes zero, and the pair is then $(g,0)$, whose common divisors are exactly the divisors of $g$. Hence the last nonzero remainder $g$ is a GCD, and every common divisor of $a$ and $b$ divides it.

Since only the degree counts, a nonzero constant multiple of a GCD is again a GCD: both $x-1$ and $2x-2$ are GCDs of $x^2-1$ and $x-1$$1$. Choosing the monic one makes the answer unique.

Because $\lambda$ is a root of a polynomial exactly when $x-\lambda$ divides it, the common roots of $a$ and $b$ are the roots of their GCD. In the Examples, $x^3-1$ and $x^2-1$ have the GCD $x-1$$1$, and $1$ is their only common root.

Key Results¶

• The last nonzero remainder is a GCD.
• The GCD is often normalized to be monic (leading coefficient $1$), which makes it unique.

Examples¶

• The GCD of $x^2-1$ and $x-1$ is $x-1$$1$.
• Euclidean algorithm: $x^3-1=x\,(x^2-1)+(x-1)$ and $x^2-1=(x+1)(x-1)+0$$0$, so the last nonzero remainder $x-1$ is the GCD of $x^3-1$ and $x^2-1$$1$.

Prerequisites¶

• Polynomial Long Division

Related Concepts¶

• Root of a Polynomial
• Polynomial
• Fundamental Theorem of Algebra

Sources¶

• Math II: Linear Algebra · Week 1

Aliases: polynomial GCD, greatest common divisor of polynomials Symbols: lambda

Last updated: 20 October 2026 03:02