Factoring polynomials

Getting back to polynomials, we know that each polynomial of degree $n$ with coefficients in a field can have at most $n$ factors. We don't yet have any strategies

(a) for finding these factors, or

(b) for determining whether or not the polynomial has any factors.

Note that a polynomial may factor yet have no roots in the field, for example $x^4+3x^2+2=(x^2+1)(x^2+2)$ has no real roots. However, if the polynomial has a root then it factors.

Definition 2.4.1   Let $F$ be a ring. A polynomial in $F[x]$ which does not factor into a product of two or more polynomials of smaller degree which also belong to $F[x]$ is called irreducible over $F$.

Irreducible polynomials are analogous to prime numbers. One of the properties of a prime number was that if $p$ was a prime and $p\vert ab$ then either $p\vert a$ or $p\vert b$ (``Euclid's First Theorem'', Proposition 1.5.8). The analogous result also holds for irreducible polynomials.

Lemma 2.4.2   Let $p(x)$ be an irreducible polynomial in $F[x]$, where $F$ is a field. If $p(x)\vert f(x)g(x)$, where $f(x),g(x)\in F[x]$, then $p(x)\vert f(x)$ or $p(x)\vert g(x)$.

The proof is analogous to the proof of Proposition 1.5.8, and so is omitted.

If a polynomial $p(x)$ has a root in $F$, say $p(c)=0$, then it is not irreducible since, by the division algorithm, $x-c$ is a factor. One would like to be able to determine whether or not a polynomial $p(x)$ is irreducible simply by means of its roots (or lack of them) in $F$. This will not work in general, as we saw with the example $x^4+3x^2+2=(x^2+1)(x^2+2)$ ( which obviously factors but has no real roots). However, if the polynomial is either a quadratic or a cubic, then it's a different story.

Lemma 2.4.3   If $p(x)$ is either a quadratic or a cubic in $F[x]$ then $p(x)$ is irreducible if and only if $p(x)$ has no roots.

proof: If $p(x)$ has degree $2$ then it can only factor into a product of two degree $1$ polynomials, each of which will have a root. If $p(x)$ has degree $3$ then it can only factor into either a product of three degree $1$ polynomials or a degree $2$ and a degree $1$ polynomial, at least one of which will have a root. $\Box$

In the previous chapter, we found out one can always factor an integer into prime powers (the fundamental theorem of arithmetic) and we considered a basic technique for factoring integers which is practical for integers of ``small'' degree. Here we want to know

• if one can always factor a polynomial over a ring or field $F$ into powers of irreducible polynomials, and

• an algorithm for factoring polynomials over $F$ which is practical at least for those of ``small'' degree.

The first issue is addressed in the next section.