Factoring Polynomials

The factorization of polynomials in algebra is the decomposition of polynomials into a product of irreducible polynomials , analogous to the prime factorization of whole numbers .

Mathematical description

The aim of factoring is a given polynomial of a polynomial a finite set of irreducible polynomials , to find with ${\displaystyle p(x)}$ ${\displaystyle R[x]}$ ${\displaystyle p_{i}\in R[x]}$ ${\displaystyle i=1,\dotsc ,n}$

${\displaystyle p(x)=p_{1}(x)\cdot p_{2}(x)\dotsm p_{n}(x)}$.

The factors do not all have to be different, that is, the factors can appear in this decomposition with a multiple greater than 1. ${\displaystyle p_{i}(x)}$

If the coefficient ring is a factorial ring , then according to a Gaussian theorem it is also factorial. In this case, there is a system of prime elements , so that this representation is unambiguous except for the sequence and association , and each is an element of the prime system. In rings that are not factorial, it is generally not possible to find a unique factorization. ${\displaystyle R}$ ${\displaystyle R[x]}$ ${\displaystyle p_{i}(x)}$

Over the field of complex numbers , each polynomial -th degree can be described as a product of precisely linear factors ${\displaystyle \mathbb {C} }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x-b_{i}}$

${\displaystyle p(x)=\sum _{k=0}^{n}a_{k}x^{k}=a_{n}\prod _{i=1}^{n}(x-b_{i})}$

write. This is one of the statements of the fundamental theorem of algebra . It is said that the polynomial breaks down into its linear factors. They are exactly the zeros of the associated polynomial function . ${\displaystyle b_{i}}$

Explanation and examples

Some polynomials can be written as the product of simpler polynomials of smaller degree. For example, factoring out and using a binomial formula results in the decomposition

${\displaystyle x^{4}-4x^{2}=x^{2}\left(x^{2}-4\right)=x^{2}(x+2)(x-2)}$.

The factors (occurs twice) and cannot be broken down further: They are irreducible . The polynomial is a divisor of the given polynomial, but it can be broken down even further. ${\displaystyle x}$ ${\displaystyle x+2}$ ${\displaystyle x-2}$ ${\displaystyle x^{2}-4}$

Whether a polynomial is irreducible or can be factored even further depends on the domain of definition of its coefficients under consideration : In the rational numbers, it cannot be further decomposed, in the real numbers it has the factorization . Another example is the polynomial : In the real numbers it is irreducible, in the complex numbers it applies with the imaginary unit . ${\displaystyle x^{2}-2}$ ${\displaystyle x^{2}-2=\left(x+{\sqrt {2}}\right)\left(x-{\sqrt {2}}\right)}$ ${\displaystyle x^{2}+1}$ ${\displaystyle x^{2}+1=(x+\mathrm {i} )(x-\mathrm {i} )}$ ${\displaystyle \mathrm {i} }$

In general: If a polynomial has a zero , it is divisible by without a remainder , that is, it applies ${\displaystyle p(x)}$ ${\displaystyle a}$ ${\displaystyle (x-a)}$

${\displaystyle p(x)=q(x)(x-a)}$

with a polynomial whose degree is smaller by one and which z. B. can be calculated by polynomial division or with the Horner scheme . If there is now a zero again, this can again be split off as a linear factor. Since a non-constant polynomial always has a zero in the complex numbers according to the fundamental theorem of algebra , this procedure ultimately leads to a factorization by decomposition into linear factors in complex calculations. ${\displaystyle q(x)}$ ${\displaystyle q(x)}$

Real polynomials

A real polynomial, on the other hand, does not always have a real zero. However, it can be understood as a complex polynomial with real coefficients. As such, it is broken down into linear factors and has the additional property that with every zero the complex conjugate number is also a zero. The two associated linear factors can be converted into the real quadratic polynomial ${\displaystyle a\in \mathbb {C} }$ ${\displaystyle {\overline {a}}}$ ${\displaystyle (x-a)(x-{\overline {a}})}$

${\displaystyle x^{2}-(a+{\overline {a}})x+a{\overline {a}}=x^{2}-2\operatorname {Re} (a)x+|a|^{2}}$

sum up. This shows that every polynomial in the real numbers can be broken down into a product of linear and quadratic factors. For example, the polynomial has the real zero and the complex conjugate zeros . In the real numbers, its factorization is . ${\displaystyle x^{3}-3x^{2}+7x-5}$ ${\displaystyle a_{1}=1}$ ${\displaystyle a_{2,3}=1\pm 2\mathrm {i} }$ ${\displaystyle (x-1)\left(x^{2}-2x+5\right)}$

Rational and integer polynomials

For polynomials with integer coefficients, there are various irreducibility criteria , such as the Eisenstein criterion , to determine whether they are irreducible in. The determination of the rational zeros of a polynomial ${\displaystyle \mathbb {Q} [x]}$

${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{1}x+a_{0}\in \mathbb {Z} [x]}$

can be solved algorithmically in a finite number of steps, because for every zero it holds that it is a divisor of and a divisor of (see theorem about rational zeros ). ${\displaystyle {\tfrac {a}{b}}\in \mathbb {Q} }$ ${\displaystyle a}$ ${\displaystyle a_{0}}$ ${\displaystyle b}$ ${\displaystyle a_{n}}$

For example, in the case of the polynomial, you can find the rational zero by trying out all the possibilities . Polynomial division results ${\displaystyle 3x^{5}-5x^{4}-6x+10}$ ${\displaystyle {\tfrac {5}{3}}}$

${\displaystyle \left(3x^{5}-5x^{4}-6x+10\right):\left(x-{\tfrac {5}{3}}\right)=3\left(x^{4}-2\right)}$

and the polynomial is irreducible according to the Eisenstein criterion (with the prime number 2), so that ultimately the integer factorization ${\displaystyle x^{4}-2}$

${\displaystyle 3x^{5}-5x^{4}-6x+10=\left(x^{4}-2\right)(3x-5)}$

results.

Algorithms

BA Hausmann described an application of Kronecker's algorithm in 1937 . Elwyn Berlekamp published the Berlekamp algorithm in 1967 , with which polynomials can be factored over the remainder class field . In 1992, Harald Niederreiter discovered another way of factoring polynomials over finite fields; the Niederreiter algorithm can be traced back to him . ${\displaystyle \mathbb {F} _{p}}$

Web links

• Online factorization tool