Dear Uncle Colin,

I have to find the greatest common divisor of $x^4 - 5x^3 + 8x^2 - 10x + 12$ and $x^4 + x^2 - 2$. How do I go about that?

- Extremely Unhappy, Clueless Learner In Distress

Hi, EUCLID, and thanks for your message!

Before we try to find the GCD of these two polynomials, it would make sense to review how we’d do it with numbers.

Factorising

Suppose we want to know the GCD of $5712$ and $10098$. One approach is to try to factorise both numbers:

  • $5712 = 2^4 \times 3 \times 7 \times 17$
  • $10098 = 2 \times 3^3 \times 11 \times 17$

You can see that both have a 2 a 3 and a 17 in common, so the greatest common factor is $2 \times 3 \times 17 = 102$.

We could do that with the polynomials - the second one in particular factorises quite nicely - but there’s another way: the Euclidean algorithm.

The Euclidean Algorithm

The idea of the Euclidean algorithm is to subtract multiples of one of the numbers from the other until you can’t go any further.

In this case:

  • $10098 = 2 \times 4992 + 114$
    • (we now see what the GCD of 4992 and 114 is)
  • $4992 = 43\times114 + 90$
    • (now 114 and 90)
  • $114 = 1\times 90 + 24$
  • $90 = 3 \times 24 + 6$
  • $24 = 4 \times 6$

… so 6 is the GCD.

This, we can do with the polynomials:

  • $x^4 + x^2 - 2 = 1 \br{x^4 - 5x^3 + 8x^2 -12x + 10} + \br{5x^3 - 7x^2 + 10x - 14}$

Now we want to find the GCD of $ \br{x^4 - 5x^3 + 8x^2 -12x + 10}$ and $\br{5x^3 - 7x^2 + 10x - 14}$. However, we’re looking for polynomial factors rather than numerical factors - we can multiply and divide by any constant we like. So I’m going to multiply the first one by 5 to make the numbers easier.

  • $5x^4 - 25x^3 +40x^2 -50x+60 = x\br{5x^3 - 7x^2 + 10x -14} + \br{-18x^3 + 30x^2 -36x + 60}$

There’s a nice factor of 6 running through the second of those, but we’ll still need to do a bit of juggling - multiply the first by 3 and the second by $-\frac{5}{6}$ to get:

  • $15x^3 - 21x^2 + 30x - 42 = \br{15x^3 - 25x^2 + 30x - 50} + \br{4x^2 + 8}$

Again, we have factors we can remove here: 5 in the first, 4 in the second:

  • $3x^3 - 5x^2 + 6x - 10 = 3x\br{x^2 + 2} + (-5x^2 - 10)$

And lastly, $-5x^2 - 10 = -5(x^2 + 2)$, so $x^2 + 2$ is the greatest common factor.

Back to factorising

I did mention that $x^4 + x^2 - 2$ factorises nicely - it’s $(x^2 + 2)(x+1)(x-1)$.

We can check two of those factors against the other quite easily using the factor theorem: does $x=1$ or $x=-1$ give us a value of 0?

If $f(x) = x^4 - 5x^3 + 8x^2 - 10x + 12$, then $f(1) = 6$ and $f(-1) = 36$, so neither of those possibilities are factors of both expression.

It would seem that $x^2 + 2$ is trickier to check, but there are two options: we could use complex numbers and check $x = \pm 2i$, or we could use polynomial division to see that $x^4 - 5x^3 + 8x^2 - 10x + 12 = (x^2+2)(x^2 -5x + 6)$ - in fact, it’s $(x^2 + 2)(x-2)(x-3)$.

In practice, factorising polynomials needs rather a lot more work, and I’d recommend the Euclidean algorithm as the first port of call.

Hope that helps!

- Uncle Colin