Factorization

Expressions

Manipulating expressions is the basis of algebra. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put an equation in a factored form E⋅F = 0, then the problem of solving the equation splits into two independent (and generally easier) problems E = 0 and F = 0. When an expression can be factored, the factors are often much simpler, and may thus offer some insight on the problem. For example, $${\displaystyle x^3-a{x}^2-b{x}^2-c{x}^2+abx+acx+bcx-abc}$$ having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression $${\displaystyle (x-a)(x-b)(x-c),}$$ with only two multiplications and three subtractions. Moreover, the factored form immediately gives roots x = a,b,c as the roots of the polynomial.

On the other hand, factorization is not always possible, and when it is possible, the factors are not always simpler. For example, ${\displaystyle x^{10}-1}$ can be factored into two irreducible factors ${\displaystyle x-1}$ and ${\displaystyle x^9+x^8+\cdots +x^2+x+1}$.

Various methods have been developed for finding factorizations; some are described below.

Solving algebraic equations may be viewed as a problem of polynomial factorization. In fact, the fundamental theorem of algebra can be stated as follows: every polynomial in x of degree n with complex coefficients may be factorized into n linear factors ${\displaystyle x-a_i,}$ for i = 1, ..., n, where the a_is are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the a_is generally cannot be computed in terms of radicals (n^th roots), by the Abel–Ruffini theorem. In most cases, the best that can be done is computing approximate values of the roots with a root-finding algorithm.

History of factorization of expressions

The systematic use of algebraic manipulations for simplifying expressions (more specifically equations) may be dated to 9th century, with al-Khwarizmi's book The Compendious Book on Calculation by Completion and Balancing, which is titled with two such types of manipulation.

However, even for solving quadratic equations, the factoring method was not used before Harriot's work published in 1631, ten years after his death. In his book Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, Harriot drew tables for addition, subtraction, multiplication and division of monomials, binomials, and trinomials. Then, in a second section, he set up the equation aa − ba + ca = + bc, and showed that this matches the form of multiplication he had previously provided, giving the factorization (a − b)(a + c).

General methods

The following methods apply to any expression that is a sum, or that may be transformed into a sum. Therefore, they are most often applied to polynomials, though they also may be applied when the terms of the sum are not monomials, that is, the terms of the sum are a product of variables and constants.

Common factor

It may occur that all terms of a sum are products and that some factors are common to all terms. In this case, the distributive law allows factoring out this common factor. If there are several such common factors, it is preferable to divide out the greatest such common factor. Also, if there are integer coefficients, one may factor out the greatest common divisor of these coefficients.

For example, $${\displaystyle 6x^3{y}^2+8x^4{y}^3-10x^5{y}^3=2x^3{y}^2(3+4xy-5x^{2}y),}$$ since 2 is the greatest common divisor of 6, 8, and 10, and ${\displaystyle x^3{y}^2}$ divides all terms.

Grouping

Grouping terms may allow using other methods for getting a factorization.

For example, to factor $${\displaystyle 4x^2+20x+3xy+15y,}$$ one may remark that the first two terms have a common factor x, and the last two terms have the common factor y. Thus $${\displaystyle 4x^2+20x+3xy+15y=(4x^2+20x)+(3xy+15y)=4x(x+5)+3y(x+5).}$$ Then a simple inspection shows the common factor x + 5, leading to the factorization $${\displaystyle 4x^2+20x+3xy+15y=(4x+3y)(x+5).}$$

In general, this works for sums of 4 terms that have been obtained as the product of two binomials. Although not frequently, this may work also for more complicated examples.

Adding and subtracting terms

Sometimes, some term grouping reveals part of a recognizable pattern. It is then useful to add and subtract terms to complete the pattern.

A typical use of this is the completing the square method for getting the quadratic formula.

Another example is the factorization of ${\displaystyle x^4+1.}$ If one introduces the non-real square root of –1, commonly denoted i, then one has a difference of squares $${\displaystyle x^4+1=(x^2+i)(x^2-i).}$$ However, one may also want a factorization with real number coefficients. By adding and subtracting ${\displaystyle 2x^2,}$ and grouping three terms together, one may recognize the square of a binomial: $${\displaystyle x^4+1=(x^4+2x^2+1)-2x^2=(x^2+1{)}^2-{\left(x\sqrt{2}\right)}^2=\left(x^2+x\sqrt{2}+1\right)\left(x^2-x\sqrt{2}+1\right).}$$ Subtracting and adding ${\displaystyle 2x^2}$ also yields the factorization: $${\displaystyle x^4+1=(x^4-2x^2+1)+2x^2=(x^2-1{)}^2+{\left(x\sqrt{2}\right)}^2=\left(x^2+x\sqrt{-2}-1\right)\left(x^2-x\sqrt{-2}-1\right).}$$ These factorizations work not only over the complex numbers, but also over any field, where either –1, 2 or –2 is a square. In a finite field, the product of two non-squares is a square; this implies that the polynomial ${\displaystyle x^4+1,}$ which is irreducible over the integers, is reducible modulo every prime number. For example, $${\displaystyle x^4+1\equiv (x+1{)}^4(\mathrm{mod}2);}$$ $${\displaystyle x^4+1\equiv (x^2+x-1)(x^2-x-1)(\mathrm{mod}3),}$$since ${\displaystyle 1^2\equiv -2(\mathrm{mod}3);}$ $${\displaystyle x^4+1\equiv (x^2+2)(x^2-2)(\mathrm{mod}5),}$$since ${\displaystyle 2^2\equiv -1(\mathrm{mod}5);}$ $${\displaystyle x^4+1\equiv (x^2+3x+1)(x^2-3x+1)(\mathrm{mod}7),}$$since ${\displaystyle 3^2\equiv 2(\mathrm{mod}7).}$

Recognizable patterns

Many identities provide an equality between a sum and a product. The above methods may be used for letting the sum side of some identity appear in an expression, which may therefore be replaced by a product.

Below are identities whose left-hand sides are commonly used as patterns (this means that the variables E and F that appear in these identities may represent any subexpression of the expression that has to be factorized).

Difference of two squares

${\displaystyle E^2-F^2=(E+F)(E-F)}$

For example,

$${\displaystyle (a+b{)}^2-(x-y{)}^2=(a+b+x-y)(a+b-x+y).}$$

Sum/difference of two cubes

${\displaystyle E^3+F^3=(E+F)(E^2-EF+F^2)}$

${\displaystyle E^3-F^3=(E-F)(E^2+EF+F^2)}$

Sum/difference of two nth powers

In the following identities, the factors may often be further factorized.See Cyclotomic polynomial for a discussion of the complete factorisation of ⁠${\displaystyle E^n\pm 1}$⁠; the factorization of ⁠${\displaystyle E^n\pm F^n}$⁠ may be deduced easily by homogenization.

Difference, even exponent

${\displaystyle E^{2n}-F^{2n}=(E^n+F^n)(E^n-F^n)}$

The factors can be further factorized with formulas that follow. Also, one may apply the next formula to ⁠${\displaystyle (E^2{)}^n-(F^2{)}^n}$⁠ for getting a factor ⁠${\displaystyle E^2-F^2=(E+F)(E-F)}$⁠.

Difference, even or odd exponent

${\displaystyle E^n-F^n=(E-F)(E^{n-1}+E^{n-2}F+E^{n-3}{F}^2+\cdots +E{F}^{n-2}+F^{n-1})=(E-F)\sum _{k=0}^{n-1}{E}^{n-1-k}{F}^k}$

This is an example showing that the factors may be much larger than the sum that is factorized.

Sum, odd exponent

${\displaystyle E^n+F^n=(E+F)(E^{n-1}-E^{n-2}F+E^{n-3}{F}^2-\cdots -E{F}^{n-2}+F^{n-1})=(E+F)\sum _{k=0}^{n-1}(-1{)}^k{E}^{n-1-k}{F}^k}$

(obtained by changing F by –F in the preceding formula)

Sum, even exponent

If the exponent is a power of two then the expression cannot, in general, be factorized without introducing complex numbers (if E and F contain complex numbers, this may be not the case). If n has an odd divisor, that is if n = pq with p odd, one may use the preceding formula (in "Sum, odd exponent") applied to ${\displaystyle (E^q{)}^p+(F^q{)}^p.}$

Sophie Germain's identity$${\displaystyle E^4+4F^4=(E^2-2EF+2F^2)(E^2+2EF+2F^2)}$$

Trinomials and cubic formulas

${\displaystyle \begin{array}{cc}& x^2+y^2+z^2+2(xy+yz+xz)=(x+y+z{)}^2\\ & x^3+y^3+z^3-3xyz=(x+y+z)(x^2+y^2+z^2-xy-xz-yz)\\ & x^3+y^3+z^3+3x^2(y+z)+3y^2(x+z)+3z^2(x+y)+6xyz=(x+y+z{)}^3\\ & x^3+y^3+z^3+3(x+y)(y+z)(x+z)=(x+y+z{)}^3\end{array}}$

Argand identity

${\displaystyle x^4+x^2{y}^2+y^4=(x^2+xy+y^2)(x^2-xy+y^2)}$

${\displaystyle x^4+x^2+1=(x^2+x+1)(x^2-x+1)}$

Binomial expansions

The binomial theorem supplies patterns that can be recognized from the integers that appear in them

In low degree:

• ${\displaystyle a^2+2ab+b^2=(a+b{)}^2}$
• ${\displaystyle a^2-2ab+b^2=(a-b{)}^2}$
• ${\displaystyle a^3+3a^{2}b+3a{b}^2+b^3=(a+b{)}^3}$
• ${\displaystyle a^3-3a^{2}b+3a{b}^2-b^3=(a-b{)}^3}$

More generally, the coefficients of the expanded forms of ${\displaystyle (a+b{)}^n}$ and ${\displaystyle (a-b{)}^n}$ are the binomial coefficients, that appear in the nth row of Pascal's triangle.

Polynomials

For polynomials, factorization is strongly related to the problem of solving algebraic equations. An algebraic equation has the form $${\displaystyle P(x)\stackrel{\text{def}}{=}{a}_0{x}^n+a_1{x}^{n-1}+\cdots +a_n=0,}$$ where P(x) is a polynomial in x with ${\displaystyle a_0\ne 0.}$ A solution of this equation (also called a root of the polynomial) is a value r of x such that $${\displaystyle P(r)=0.}$$

If ${\displaystyle P(x)=Q(x)R(x)}$ is a factorization of P(x) = 0 as a product of two polynomials, then the roots of P(x) are the union of the roots of Q(x) and the roots of R(x). Thus solving P(x) = 0 is reduced to the simpler problems of solving Q(x) = 0 and R(x) = 0.

Conversely, the factor theorem asserts that, if r is a root of P(x) = 0, then P(x) may be factored as $${\displaystyle P(x)=(x-r)Q(x),}$$ where Q(x) is the quotient of Euclidean division of P(x) = 0 by the linear (degree one) factor x − r.

If the coefficients of P(x) are real or complex numbers, the fundamental theorem of algebra asserts that P(x) has a real or complex root. Using the factor theorem recursively, it results that $${\displaystyle P(x)=a_0(x-r_1)\cdots (x-r_n),}$$ where ${\displaystyle r_1,\dots ,r_n}$ are the real or complex roots of P, with some of them possibly repeated. This complete factorization is unique up to the order of the factors.

If the coefficients of P(x) are real, one generally wants a factorization where factors have real coefficients. In this case, the complete factorization may have some quadratic (degree two) factors. This factorization may easily be deduced from the above complete factorization. In fact, if r = a + ib is a non-real root of P(x), then its complex conjugate s = a − ib is also a root of P(x). So, the product $${\displaystyle (x-r)(x-s)=x^2-(r+s)x+rs=x^2-2ax+a^2+b^2}$$ is a factor of P(x) with real coefficients. Repeating this for all non-real factors gives a factorization with linear or quadratic real factors.

For computing these real or complex factorizations, one needs the roots of the polynomial, which may not be computed exactly, and only approximated using root-finding algorithms.

In practice, most algebraic equations of interest have integer or rational coefficients, and one may want a factorization with factors of the same kind. The fundamental theorem of arithmetic may be generalized to this case, stating that polynomials with integer or rational coefficients have the unique factorization property. More precisely, every polynomial with rational coefficients may be factorized in a product $${\displaystyle P(x)=q{P}_1(x)\cdots P_k(x),}$$ where q is a rational number and ${\displaystyle P_1(x),\dots ,P_k(x)}$ are non-constant polynomials with integer coefficients that are irreducible and primitive; this means that none of the ${\displaystyle P_i(x)}$ may be written as the product two polynomials (with integer coefficients) that are neither 1 nor −1 (integers are considered as polynomials of degree zero). Moreover, this factorization is unique up to the order of the factors and the signs of the factors.

There are efficient algorithms for computing this factorization, which are implemented in most computer algebra systems. See Factorization of polynomials. Unfortunately, these algorithms are too complicated to use for paper-and-pencil computations. Besides the heuristics above, only a few methods are suitable for hand computations, which generally work only for polynomials of low degree, with few nonzero coefficients. The main such methods are described in next subsections.

Primitive-part & content factorization

Every polynomial with rational coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which is primitive (that is, the greatest common divisor of the coefficients is 1), and has a positive leading coefficient (coefficient of the term of the highest degree). For example: $${\displaystyle -10x^2+5x+5=(-5)\cdot (2x^2-x-1)}$$ $${\displaystyle \frac{1}{3}{x}^5+\frac{7}{2}{x}^2+2x+1=\frac{1}{6}(2x^5+21x^2+12x+6)}$$

In this factorization, the rational number is called the content, and the primitive polynomial is the primitive part. The computation of this factorization may be done as follows: firstly, reduce all coefficients to a common denominator, for getting the quotient by an integer q of a polynomial with integer coefficients. Then one divides out the greater common divisor p of the coefficients of this polynomial for getting the primitive part, the content being ${\displaystyle p/q.}$ Finally, if needed, one changes the signs of p and all coefficients of the primitive part.

This factorization may produce a result that is larger than the original polynomial (typically when there are many coprime denominators), but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.

Using the factor theorem

The factor theorem states that, if r is a root of a polynomial $${\displaystyle P(x)=a_0{x}^n+a_1{x}^{n-1}+\cdots +a_{n-1}x+a_n,}$$ meaning P(r) = 0, then there is a factorization $${\displaystyle P(x)=(x-r)Q(x),}$$ where $${\displaystyle Q(x)=b_0{x}^{n-1}+\cdots +b_{n-2}x+b_{n-1},}$$ with ${\displaystyle a_0=b_0}$. Then polynomial long division or synthetic division give: $${\displaystyle b_i=a_0{r}^i+\cdots +a_{i-1}r+a_i\text{ for }i=1,\dots ,n-1.}$$ This may be useful when one knows or can guess a root of the polynomial.

For example, for ${\displaystyle P(x)=x^3-3x+2,}$ one may easily see that the sum of its coefficients is 0, so r = 1 is a root. As r + 0 = 1, and ${\displaystyle r^2+0r-3=-2,}$ one has $${\displaystyle x^3-3x+2=(x-1)(x^2+x-2).}$$

Rational roots

For polynomials with rational number coefficients, one may search for roots which are rational numbers. Primitive part-content factorization (see above) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivial common divisor.

If ${\displaystyle x=\frac{p}{q}}$ is a rational root of such a polynomial $${\displaystyle P(x)=a_0{x}^n+a_1{x}^{n-1}+\cdots +a_{n-1}x+a_n,}$$ the factor theorem shows that one has a factorization $${\displaystyle P(x)=(qx-p)Q(x),}$$ where both factors have integer coefficients (the fact that Q has integer coefficients results from the above formula for the quotient of P(x) by ${\displaystyle x-p/q}$).

Comparing the coefficients of degree n and the constant coefficients in the above equality shows that, if ${\displaystyle \frac{p}{q}}$ is a rational root in reduced form, then q is a divisor of ${\displaystyle a_0,}$ and p is a divisor of ${\displaystyle a_n.}$ Therefore, there is a finite number of possibilities for p and q, which can be systematically examined.

For example, if the polynomial $${\displaystyle P(x)=2x^3-7x^2+10x-6}$$ has a rational root ${\displaystyle \frac{p}{q}}$ with q > 0, then p must divide 6; that is ${\displaystyle p\in \{\pm 1,\pm 2,\pm 3,\pm 6\},}$ and q must divide 2, that is ${\displaystyle q\in \{1,2\}.}$ Moreover, if x < 0, all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have $${\displaystyle \frac{p}{q}\in \{1,2,3,6,\frac{1}{2},\frac{3}{2}\}.}$$ A direct computation shows that only ${\displaystyle \frac{3}{2}}$ is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization ${\displaystyle 2x^3-7x^2+10x-6=(2x-3)(x^2-2x+2).}$

Quadratic ac method

The above method may be adapted for quadratic polynomials, leading to the ac method of factorization.

Consider the quadratic polynomial $${\displaystyle P(x)=a{x}^2+bx+c}$$ with integer coefficients. If it has a rational root, its denominator must divide a evenly and it may be written as a possibly reducible fraction ${\displaystyle r_1=\frac{r}{a}.}$ By Vieta's formulas, the other root ${\displaystyle r_2}$ is $${\displaystyle r_2=-\frac{b}{a}-r_1=-\frac{b}{a}-\frac{r}{a}=-\frac{b+r}{a}=\frac{s}{a},}$$ with ${\displaystyle s=-(b+r).}$ Thus the second root is also rational, and Vieta's second formula ${\displaystyle r_1{r}_2=\frac{c}{a}}$ gives $${\displaystyle \frac{s}{a}\frac{r}{a}=\frac{c}{a},}$$ that is $${\displaystyle rs=ac\text{and}r+s=-b.}$$ Checking all pairs of integers whose product is ac gives the rational roots, if any.

In summary, if ${\displaystyle a{x}^2+bx+c}$ has rational roots there are integers r and s such ${\displaystyle rs=ac}$ and ${\displaystyle r+s=-b}$ (a finite number of cases to test), and the roots are ${\displaystyle \frac{r}{a}}$ and ${\displaystyle \frac{s}{a}.}$ In other words, one has the factorization $${\displaystyle a(a{x}^2+bx+c)=(ax-r)(ax-s).}$$

For example, let consider the quadratic polynomial $${\displaystyle 6x^2+13x+6.}$$ Inspection of the factors of ac = 36 leads to 4 + 9 = 13 = b, giving the two roots $${\displaystyle r_1=-\frac{4}{6}=-\frac{2}{3}\text{and}{r}_2=-\frac{9}{6}=-\frac{3}{2},}$$

and the factorization $${\displaystyle 6x^2+13x+6=6(x+\frac{2}{3})(x+\frac{3}{2})=(3x+2)(2x+3).}$$

Using formulas for polynomial roots

Any univariate quadratic polynomial ${\displaystyle a{x}^2+bx+c}$ can be factored using the quadratic formula: $${\displaystyle a{x}^2+bx+c=a(x-\alpha )(x-\beta )=a\left(x-\frac{-b+\sqrt{b^2-4ac}}{2a}\right)\left(x-\frac{-b-\sqrt{b^2-4ac}}{2a}\right),}$$ where ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are the two roots of the polynomial.

If a, b, c are all real, the factors are real if and only if the discriminant ${\displaystyle b^2-4ac}$ is non-negative. Otherwise, the quadratic polynomial cannot be factorized into non-constant real factors.

The quadratic formula is valid when the coefficients belong to any field of characteristic different from two, and, in particular, for coefficients in a finite field with an odd number of elements.

There are also formulas for roots of cubic and quartic polynomials, which are, in general, too complicated for practical use. The Abel–Ruffini theorem shows that there are no general root formulas in terms of radicals for polynomials of degree five or higher.

Using relations between roots

It may occur that one knows some relationship between the roots of a polynomial and its coefficients. Using this knowledge may help factoring the polynomial and finding its roots. Galois theory is based on a systematic study of the relations between roots and coefficients, that include Vieta's formulas.

Here, we consider the simpler case where two roots ${\displaystyle x_1}$ and ${\displaystyle x_2}$ of a polynomial ${\displaystyle P(x)}$ satisfy the relation $${\displaystyle x_2=Q(x_1),}$$ where Q is a polynomial.

This implies that ${\displaystyle x_1}$ is a common root of ${\displaystyle P(Q(x))}$ and ${\displaystyle P(x).}$ It is therefore a root of the greatest common divisor of these two polynomials. It follows that this greatest common divisor is a non constant factor of ${\displaystyle P(x).}$ Euclidean algorithm for polynomials allows computing this greatest common factor.

For example, if one know or guess that: ${\displaystyle P(x)=x^3-5x^2-16x+80}$ has two roots that sum to zero, one may apply Euclidean algorithm to ${\displaystyle P(x)}$ and ${\displaystyle P(-x).}$ The first division step consists in adding ${\displaystyle P(x)}$ to ${\displaystyle P(-x),}$ giving the remainder of $${\displaystyle -10(x^2-16).}$$ Then, dividing ${\displaystyle P(x)}$ by ${\displaystyle x^2-16}$ gives zero as a new remainder, and x − 5 as a quotient, leading to the complete factorization $${\displaystyle x^3-5x^2-16x+80=(x-5)(x-4)(x+4).}$$

Unique factorization domains

The integers and the polynomials over a field share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a unit, ±1 in the case of integers) and a product of irreducible elements (prime numbers, in the case of integers), and this factorization is unique up to rearranging the factors and shifting units among the factors. Integral domains which share this property are called unique factorization domains (UFD).

Greatest common divisors exist in UFDs, but not every integral domain in which greatest common divisors exist (known as a GCD domain) is a UFD. Every principal ideal domain is a UFD.

A Euclidean domain is an integral domain on which is defined a Euclidean division similar to that of integers. Every Euclidean domain is a principal ideal domain, and thus a UFD.

In a Euclidean domain, Euclidean division allows defining a Euclidean algorithm for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of a field F such that there cannot exist any factorization algorithm in the Euclidean domain F[x] of the univariate polynomials over F.

Ideals

In algebraic number theory, the study of Diophantine equations led mathematicians, during 19th century, to introduce generalizations of the integers called algebraic integers. The first ring of algebraic integers that have been considered were Gaussian integers and Eisenstein integers, which share with usual integers the property of being principal ideal domains, and have thus the unique factorization property.

Unfortunately, it soon appeared that most rings of algebraic integers are not principal and do not have unique factorization. The simplest example is ${\displaystyle \mathbb{Z}[\sqrt{-5}],}$ in which

$${\displaystyle 9=3\cdot 3=(2+\sqrt{-5})(2-\sqrt{-5}),}$$

and all these factors are irreducible.

This lack of unique factorization is a major difficulty for solving Diophantine equations. For example, many wrong proofs of Fermat's Last Theorem (probably including Fermat's "truly marvelous proof of this, which this margin is too narrow to contain") were based on the implicit supposition of unique factorization.

This difficulty was resolved by Dedekind, who proved that the rings of algebraic integers have unique factorization of ideals: in these rings, every ideal is a product of prime ideals, and this factorization is unique up the order of the factors. The integral domains that have this unique factorization property are now called Dedekind domains. They have many nice properties that make them fundamental in algebraic number theory.

Matrices

Matrix rings are non-commutative and have no unique factorization: there are, in general, many ways of writing a matrix as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the LU decomposition gives a matrix as the product of a lower triangular matrix by an upper triangular matrix. As this is not always possible, one generally considers the "LUP decomposition" having a permutation matrix as its third factor.

See Matrix decomposition for the most common types of matrix factorizations.

A logical matrix represents a binary relation, and matrix multiplication corresponds to composition of relations. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a difunctional relation.