Factorization

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x − 2)(x + 2) is a polynomial factorization of x − 4.

Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any \(x\) can be trivially written as \((xy)\times(1/y)\) whenever \(y\) is not zero. However, a meaningful factorization for a rational number or a rational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator.

Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factored into a product of prime numbers, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique up to the order of the factors. Although integer factorization is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the RSA cryptosystem to implement public-key cryptography.

Polynomial factorization has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its roots to finding the roots of the factors. Polynomials with coefficients in the integers or in a field possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by irreducible polynomials. In particular, a univariate polynomial with complex coefficients admits a unique (up to ordering) factorization into linear polynomials: this is a version of the fundamental theorem of algebra. In this case, the factorization can be done with root-finding algorithms. The case of polynomials with integer coefficients is fundamental for computer algebra. There are efficient computer algorithms for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see factorization of polynomials).

A commutative ring possessing the unique factorization property is called a unique factorization domain. There are number systems, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of Dedekind domains: ideals factor uniquely into prime ideals.

Factorization may also refer to more general decompositions of a mathematical object into the product of smaller or simpler objects. For example, every function may be factored into the composition of a surjective function with an injective function. Matrices possess many kinds of matrix factorizations. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix L with all diagonal entries equal to one, an upper triangular matrix U, and a permutation matrix P; this is a matrix formulation of Gaussian elimination.

By the fundamental theorem of arithmetic, every integer greater than 1 has a unique (up to the order of the factors) factorization into prime numbers, which are those integers which cannot be further factorized into the product of integers greater than one.

For computing the factorization of an integer n, one needs an algorithm for finding a divisor q of n or deciding that n is prime. When such a divisor is found, the repeated application of this algorithm to the factors q and n / q gives eventually the complete factorization of n.

For finding a divisor q of n, if any, it suffices to test all values of q such that 1 < q and q ≤ n. In fact, if r is a divisor of n such that r > n, then q = n / r is a divisor of n such that q ≤ n.

If one tests the values of q in increasing order, the first divisor that is found is necessarily a prime number, and the cofactor r = n / q cannot have any divisor smaller than q. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of r that is not smaller than q and not greater than √r.

There is no need to test all values of q for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the sieve of Eratosthenes. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3.

This method works well for factoring small integers, but is inefficient for larger integers. For example, Pierre de Fermat was unable to discover that the 6th Fermat number

\(1 + 2^{2^5} = 1 + 2^{32} = 4\,294\,967\,297\)

is not a prime number. In fact, applying the above method would require more than 10000 divisions, for a number that has 10 decimal digits.

Condensed — the full section is in Wikipedia.

For factoring n = 1386 into primes:

• Start with division by 2: the number is even, and n = 2 · 693. Continue with 693, and 2 as a first divisor candidate.
• 693 is odd (2 is not a divisor), but is a multiple of 3: one has 693 = 3 · 231 and n = 2 · 3 · 231. Continue with 231, and 3 as a first divisor candidate.
• 231 is also a multiple of 3: one has 231 = 3 · 77, and thus n = 2 · 3 · 77. Continue with 77, and 3 as a first divisor candidate.
• 77 is not a multiple of 3, since the sum of its digits is 14, not a multiple of 3. It is also not a multiple of 5 because its last digit is 7. The next odd divisor to be tested is 7. One has 77 = 7 · 11, and thus n = 2 · 3 · 7 · 11. This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate.
• As 7 > 11, one has finished. Thus 11 is prime, and the prime factorization is

1386 = 2 · 3 · 7 · 11.

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,

\(x^3-ax^2-bx^2-cx^2+ abx+acx+bcx-abc\)

having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression

\((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, \(x^{10}-1\) can be factored into two irreducible factors \(x-1\) and \(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 \(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 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.

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).

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.

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

\(E^2 - F^2 = (E+F)(E-F)\)

For example,

\((a+b)^2 - (x -y)^2 = (a+b + x -y)(a+b -x + y).\)

• Sum/difference of two cubes

\(E^3 + F^3 = (E + F)(E^2 - EF + F^2)\)

\(E^3 - F^3 = (E - F)(E^2 + EF + F^2)\)

• Cauchy identity

\(a^3 + b^3 + 3ab(a+b) = (a+b)^3\)

\(a^3 - b^3 - 3ab(a-b) = (a-b)^3\)

• Difference of two fourth powers

\(\begin{align} E^4 - F^4 &= (E^2 + F^2)(E^2 - F^2) \\ &= (E^2 + F^2)(E + F)(E - F) \end{align}\)

• Sum/difference of two nth powers

In the following identities, the factors may often be further factorized:

• Difference, even exponent

\(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 ⁠\((E^2)^n-(F^2)^n\)⁠ for getting a factor ⁠\(E^2-F^2=(E+F)(E-F)\)⁠.

• Difference, even or odd exponent

\(E^n - F^n = (E-F)(E^{n-1} + E^{n-2}F + E^{n-3}F^2 + \cdots + EF^{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

\(E^n + F^n = (E+F)(E^{n-1} - E^{n-2}F + E^{n-3}F^2 - \cdots - EF^{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 \((E^q)^p+(F^q)^p.\)

• Trinomials and cubic formulas

\(\begin{align} &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{align}\)

• Argand identity

\(x^4 + x^2y^2 + y^4 = (x^2 + xy +y^2)(x^2 - xy + y^2)\)

\(x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)\)

• Binomial expansions

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

In low degree:

\(a^2 + 2ab + b^2 = (a + b)^2\)

\(a^2 - 2ab + b^2 = (a - b)^2\)

\(a^3 + 3a^2b + 3ab^2 + b^3 = (a+b)^3\)

\(a^3 - 3a^2b + 3ab^2 - b^3 = (a-b)^3\)

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

For polynomials, factorization is strongly related to the problem of solving algebraic equations. An algebraic equation has the form

\(P(x)\ \,\stackrel{\text{def}}{=}\ \,a_0x^n+a_1x^{n-1}+\cdots+a_n=0,\)

where P(x) is a polynomial in x with \(a_0\ne 0.\) A solution of this equation (also called a root of the polynomial) is a value r of x such that

\(P(r)=0.\)

If \(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

\(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

\(P(x)=a_0(x-r_1)\cdots (x-r_n),\)

where \(r_1, \ldots, 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.

\((x-r)(x-s) = x^2-(r+s)x+rs = x^2-2ax+a^2+b^2\)

\(P(x)=q\,P_1(x)\cdots P_k(x),\)

Condensed — the full section is in Wikipedia.

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:

\(-10x^2 + 5x + 5 = (-5)\cdot (2x^2 - x - 1)\)

\(\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 \(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.

The factor theorem states that, if r is a root of a polynomial

\(P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,\)

meaning P(r) = 0, then there is a factorization

\(P(x)=(x-r)Q(x),\)

where

\(Q(x)=b_0x^{n-1}+\cdots+b_{n-2}x+b_{n-1},\)

with \(a_0=b_0\). Then polynomial long division or synthetic division give:

\(b_i=a_0r^i +\cdots+a_{i-1}r+a_i \ \text{ for }\ i = 1,\ldots,n{-}1.\)

This may be useful when one knows or can guess a root of the polynomial.

For example, for \(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 \(r^2 +0r-3=-2,\) one has

\(x^3 - 3x + 2 = (x - 1)(x^2 + x - 2).\)

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 \(x=\tfrac pq\) is a rational root of such a polynomial

\(P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,\)

the factor theorem shows that one has a factorization

\(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 \(x-p/q\)).

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

For example, if the polynomial

\(P(x)=2x^3 - 7x^2 + 10x - 6\)

has a rational root \(\tfrac pq\) with q > 0, then p must divide 6; that is \(p\in\{\pm 1,\pm 2,\pm3, \pm 6\},\) and q must divide 2, that is \(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

\(\tfrac pq \in \{1, 2, 3, 6, \tfrac 12, \tfrac 32\}.\)

Condensed — the full section is in Wikipedia.

Any univariate quadratic polynomial \(ax^2+bx+c\) can be factored using the quadratic formula:

\(ax^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 \(\alpha\) and \(\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 \(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.

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 \(x_1\) and \(x_2\) of a polynomial \(P(x)\) satisfy the relation

\(x_2=Q(x_1),\)

where Q is a polynomial.

This implies that \(x_1\) is a common root of \(P(Q(x))\) and \(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 \(P(x).\) Euclidean algorithm for polynomials allows computing this greatest common factor.

For example, if one know or guess that: \(P(x)=x^3 -5x^2 -16x +80\) has two roots that sum to zero, one may apply Euclidean algorithm to \(P(x)\) and \(P(-x).\) The first division step consists in adding \(P(x)\) to \(P(-x),\) giving the remainder of

\(-10(x^2-16).\)

Then, dividing \(P(x)\) by \(x^2-16\) gives zero as a new remainder, and x − 5 as a quotient, leading to the complete factorization

\(x^3 - 5x^2 - 16x + 80 = (x -5)(x-4)(x+4).\)

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.