Factorization of polynomials

Various techniques have been developed to factor polynomials. From a theoretical perspective, the problem can be regarded as completely solved by means of the fundamental theorem of algebra, which states that all polynomials with complex coefficients have complex roots, i.e, they can be completely factored over the complex field C. From a more practical vantage point, the fundamental theorem is only an existance proof that offers little insight into the common problem of actually finding the roots of a given polynomial.

Factoring over Q and Z

It can be shown that factoring over Q (the rational numbers) can be reduced to factoring over Z (the integers). This is a specific example of a more general case — factoring over a quotient field can be reduced to factoring over the corresponding integral ___domain.

The classic proof, due to Gauss, first factors a polynomial into its content, a rational number, and its primitive part, a polynomial whose coefficients are pure integers and share no common divisor among them. Any polynomial with rational coefficients can be factored in this way, using a content composed of the greatest common divisor of the numerators, and the least common multiple of the denominators. This factorization is unique.

For example,

${\displaystyle 10x^{2}+5x+5=5(2x^{2}+x+1)\,}$ 

and

${\displaystyle {\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6)}$ 

since ${\displaystyle \mathrm {GCD} (1,7,2,1)=1}$  and ${\displaystyle \mathrm {LCM} (3,2)=6}$ .

Theorem: The product of two primitive polynomials is itself primitive.

Proof:

Clearly the product ${\displaystyle f(x)\cdot g(x)}$  of two primitive polynomials has integral coefficients. Therefore, if it is not primitive, there must be a common divisor ${\displaystyle d}$  of all its coefficients, that can not divide all the coefficients of either ${\displaystyle f(x)}$  or ${\displaystyle g(x)}$  (otherwise they would not be primitive). Let ${\displaystyle a_{r}x^{r}}$  be the first coefficient of ${\displaystyle f(x)}$  not divisible by ${\displaystyle d}$  and let ${\displaystyle b_{s}x^{s}}$  be the first coefficient of ${\displaystyle g(x)}$  not divisible by ${\displaystyle d}$ . Now consider the term ${\displaystyle x^{r+s}}$  in the product. Its coefficient must take the form:

${\displaystyle a_{r}b_{s}+a_{r+1}b_{s-1}+a_{r+2}b_{s-2}+\ldots +a_{r-1}b_{s+1}+a_{r-2}b_{s+2}+\ldots }$ 

The first term is not divisible by ${\displaystyle d}$ , yet all the remaining ones are, so the entire sum must not be divisble by ${\displaystyle d}$ . Yet we assumed that all coefficients in the product were divisible by ${\displaystyle d}$ , a contridiction. Therefore, the coefficients of the product can have no common divisor and are thus primitive.

QED

Now, any polynomial with rational coefficients can be split into a content and a primitive polynomial, and in particular the factors of any factorization (over Q) of such a polynomial can also be so split. Since the content and the primitive polynomials are unique, and since the product of primitive polynomials is itself primitive, the primitive part of the polynomial must factor into the primitive parts of the factors. In particular, if a polynomial with integer coefficients can be factored at all, it can be factored into integer polynomials. So factoring a polynomial with rational coefficients can be reduced to finding integer factorizations of its primitive part.

Currently the best techniques for factoring integer polynomials involve factoring over finite fields, but a simpler technique is usable for small polynomials (roughly less than tenth degree), if a computer is used. Since integer polynomials must factor into integer polynomial factors, and evaluating integer polynomials at integer values must produce integers, the integer values of a polynomial can be factored in only a finite number of ways, and produce only a finite number of possible polynomial factors.

For example, consider ${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$ . If this polynomial factors over Z, then at least one of its factors must be of degree two or less. We need three values to uniquely fit a second degree polynomial. We'll use ${\displaystyle f(0)=2}$ , ${\displaystyle f(1)=6}$  and ${\displaystyle f(-1)=2}$ . Now, 2 can factor as either 1×2, 2×1, -1×-2, or -2×-1. Therefore, if a second degree integer polynomial factor exists, it must take one of the values 1, 2, -1, or -2 at ${\displaystyle x=0}$ , and likewise at ${\displaystyle x=-1}$ . There are eight different ways to factor 6, so there are 4×4×8 = 64 possible combinations, of which half can be discarded as the negatives of the other half, corresponding to 32 possible second degree integer polynomials which must be checked. These are the only possible integer polynomial factors of ${\displaystyle f(x)}$ . Testing them exhaustively reveals that ${\displaystyle g(x)=x^{2}+x+1}$ , constructed from ${\displaystyle g(0)=1}$ , ${\displaystyle g(1)=2}$  and ${\displaystyle g(-1)=1}$ , factors ${\displaystyle f(x)}$ .

(Van der Waerden, Sections 5.4 and 5.6)

Factoring over ${\displaystyle Z_{n}}$

Berklekamp's algorithm.

Factoring over algebraic extensions

Bibliography

• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.