# 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 (xa)}$

${\ displaystyle p (x) = q (x) (xa)}$

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 (xa) (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}}$