Greatest Common Divisor of Polynomials

The greatest common divisor (GCD) of two or more polynomials is the polynomial of highest possible degree that divides each of them exactly.

How to compute the GCD of polynomials

To determine the GCD of a set of polynomials:

Factor each polynomial completely into irreducible components using irreducible factorization.
Identify the common factors across all the polynomials and multiply them together, including each factor only once and with its lowest exponent.

Note. There's a clear analogy between the GCD of integers and that of polynomials. In both cases, we begin by factoring into irreducibles, then select the common factors at their minimal degrees and multiply them together.

A worked example

Consider the following polynomials:

$$ A(x): 6x^3 $$

$$ B(x): 3x^4 - 27x^2 $$

$$ C(x): 2x^3 + 6x^2 $$

We first express them in fully factored form:

$$ A(x): 2 \cdot 3 \cdot x^3 $$

$$ B(x): 3 \cdot x^2 \cdot (x - 3) \cdot (x + 3) $$

$$ C(x): 2 \cdot x^2 \cdot (x + 3) $$

Explanation. The factorization of A(x) is straightforward: $$ A(x): 6x^3 $$ We simply break down the coefficient: $$ A(x): 2 \cdot 3 \cdot x^3 $$ For B(x), we start with $$ B(x): 3x^4 - 27x^2 $$ Since all terms are divisible by 3, we factor it out: $$ B(x): 3 \cdot (x^4 - 9x^2) $$ Then factor out $ x^2 $: $$ B(x): 3 \cdot x^2 \cdot (x^2 - 3^2) $$ Finally, we apply the difference of squares: $$ B(x): 3 \cdot x^2 \cdot (x - 3) \cdot (x + 3) $$ For C(x): $$ C(x): 2x^3 + 6x^2 $$ We begin by factoring out the 2: $$ C(x): 2 \cdot (x^3 + 3x^2) $$ Then factor out $ x^2 $: $$ C(x): 2 \cdot x^2 \cdot (x + 3) $$

$$ \begin{vmatrix} A(x) & 2 & 3 & x^3 \\ B(x) & & 3 & x^2 & x - 3 & x + 3 \\ C(x) & 2 & & x^2 & & x + 3 \end{vmatrix} $$

We now look for the factors common to all three polynomials.

Here, it's the third column: the powers of $ x $.

$$ \begin{vmatrix} A(x) & 2 & 3 & \color{red}{x^3} \\ B(x) & & 3 & \color{red}{x^2} & x - 3 & x + 3 \\ C(x) & 2 & & \color{red}{x^2} & & x + 3 \end{vmatrix} $$

We take only the lowest power of the common factor, which is $ x^2 $.

Since there are no other shared factors (1 is understood), the GCD of the three polynomials is x²

$$ \text{GCD}[A(x), B(x), C(x)] = x^2 $$

The polynomial $ x^2 $ is the highest-degree polynomial that divides all of A(x), B(x), and C(x) exactly.

Example 2

Now let’s look at another set of polynomials:

$$ A(x): 3x^2y + 3xy^2 $$

$$ B(x): 6x^3 + 6x^2y $$

$$ C(x): 2x^2y^2 + 2xy^3 $$

We factor each one:

$$ A(x): 3 \cdot x \cdot y \cdot (x + y) $$

$$ B(x): 2 \cdot 3 \cdot x^2 \cdot (x + y) $$

$$ C(x): 2 \cdot x \cdot y^2 \cdot (x + y) $$

Explanation. Starting with A(x): $$ A(x): 3x^2y + 3xy^2 $$ First, factor out 3: $$ A(x): 3 \cdot (x^2y + xy^2) $$ Then factor out $ x $: $$ A(x): 3 \cdot x \cdot (xy + y^2) $$ Finally, factor out $ y $: $$ A(x): 3 \cdot x \cdot y \cdot (x + y) $$ For B(x): $$ B(x): 6x^3 + 6x^2y $$ $$ B(x): 6 \cdot (x^3 + x^2y) $$ $$ B(x): 2 \cdot 3 \cdot x^2 \cdot (x + y) $$ For C(x):
$$ C(x): 2x^2y^2 + 2xy^3 $$ $$ C(x): 2 \cdot (x^2y^2 + xy^3) $$ $$ C(x): 2 \cdot x \cdot (xy^2 + y^3) $$ $$ C(x): 2 \cdot x \cdot y^2 \cdot (x + y) $$

$$ \begin{vmatrix} A(x) & & 3 & x & y & x + y \\ B(x) & 2 & 3 & x^2 & & x + y \\ C(x) & 2 & & x & y^2 & x + y \end{vmatrix} $$

Here, we find two factors common to all three polynomials.

From the table, both the fourth column ($ x $) and sixth column ($ x + y $) appear in every factorization.

$$ \begin{vmatrix} A(x) & & 3 & \color{red}{x} & y & \color{red}{x + y} \\ B(x) & 2 & 3 & \color{red}{x^2} & & \color{red}{x + y} \\ C(x) & 2 & & \color{red}{x} & y^2 & \color{red}{x + y} \end{vmatrix} $$

We again select the lowest powers of the common factors - $ x $ and $ x + y $ - and multiply them together.

So, the GCD of these three polynomials is x(x + y)

$$ \text{GCD}[A(x), B(x), C(x)] = x \cdot (x + y) $$

The polynomial $ x(x + y) $ is the highest-degree polynomial that divides A(x), B(x), and C(x) without remainder.

And so on.