Factorization

From Wikipedia, the free encyclopedia
  (Redirected from Factorisation)
Jump to: navigation, search
This article is about the mathematical concept. For other uses, see Factor and Integer factorization.
The polynomial x2 + cx + d, where a + b = c and ab = d, can be factorized into (x + a)(x + b).

In mathematics, factorization (also factorisation in some forms of British English) or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. For example, the number 15 factors into primes as 3 × 5, and the polynomial x2 − 4 factors as (x − 2)(x + 2). In all cases, a product of simpler objects is obtained.

The aim of factoring is usually to reduce something to “basic building blocks”, such as numbers to prime numbers, or polynomials to irreducible polynomials. Factoring integers is covered by the fundamental theorem of arithmetic and factoring polynomials by the fundamental theorem of algebra. Viète's formulas relate the coefficients of a polynomial to its roots.

The opposite of polynomial factorization is expansion, the multiplying together of polynomial factors to an “expanded” polynomial, written as just a sum of terms.

Integer factorization for large integers appears to be a difficult problem. There is no known method to carry it out quickly. Its complexity is the basis of the assumed security of some public key cryptography algorithms, such as RSA.

A matrix can also be factorized into a product of matrices of special types, for an application in which that form is convenient. One major example of this uses an orthogonal or unitary matrix, and a triangular matrix. There are different types: QR decomposition, LQ, QL, RQ, RZ.

Another example is the factorization of a function as the composition of other functions having certain properties; for example, every function can be viewed as the composition of a surjective function with an injective function. This situation is generalized by factorization systems.

Integers[edit]

Main article: Integer factorization

By the fundamental theorem of arithmetic, every positive integer greater than 1 has a unique prime factorization. Given an algorithm for integer factorization, one can factor any integer down to its constituent primes by repeated application of this algorithm.[1] For very large numbers, no efficient classical algorithm is known.

Polynomials[edit]

Modern techniques for factoring polynomials are fast and efficient, but use sophisticated mathematical ideas (see Factorization of polynomials). These techniques are used in the construction of computer routines for carrying out polynomial factorization in Computer algebra systems. The more classical hand techniques rely on either the polynomial to be factored having low degree or the recognition of the polynomial as belonging to a certain class of known examples and are not very suitable for computer implementation. This article is concerned with these classical techniques.

While the general notion of factoring just means writing an expression as a product of simpler expressions, the vague term "simpler" will be defined more precisely for special classes of expressions. When factoring polynomials this means that the factors are to be polynomials of smaller degree. Thus, while x^2 - y = (x + \sqrt{y})(x - \sqrt{y}) is a factorization of the expression, it is not a polynomial factorization since the factors are not polynomials.[2] Also, the factoring of a constant term, as in 3x^2 -6x + 12 = 3(x^2 - 2x + 4) would not be considered a polynomial factorization since one of the factors does not have a smaller degree than the original expression.[3] Another issue concerns the coefficients of the factors. In basic treatments it is desirable to have the coefficients of the factors be of the same type as the coefficients of the original polynomial, that is factoring polynomials with integer coefficients into factors with integer coefficients, or factoring polynomials with real coefficients into polynomials with real coefficients. It is not always possible to do this, and a polynomial that can not be factored in this way is said to be irreducible over this type of coefficient. Thus, x2 -2 is irreducible over the integers and x2 + 4 is irreducible over the reals. In the first example, the integers 1 and -2 can also be thought of as real numbers, and if they are, then x^2 -2 = (x + \sqrt{2})(x - \sqrt{2}) shows that this polynomial factors over the reals (sometimes it is said that the polynomial splits over the reals). Similarly, since the integers 1 and 4 can be thought of as real and hence complex numbers, x2 + 4 splits over the complex numbers, i.e. x^2 + 4 = (x + 2i)(x - 2i).

The Fundamental theorem of algebra can be stated as: Every polynomial of degree n with complex number coefficients splits completely into n linear factors.[4] Since complex roots of polynomials with real coefficients come in conjugate pairs, this result implies that every polynomial with real coefficients splits into linear and irreducible quadratic factors with real coefficients. Even though the structure of the factorization is known in these cases, finding the actual factors can be computationally challenging.

General methods[edit]

There are only a few general methods that can be applied to any polynomial in either one variable (the univariate case) or several variables (the multivariate case).

Highest common factor[edit]

Finding, by inspection, the monomial that is the highest common factor (also called the greatest common divisor) of all the terms of the polynomial and factoring it out as a common factor is an application of the distributive law. This is the most commonly used factoring technique. For example:[5]

6x^3y^2 + 8x^4y^3 - 10x^5y^3 = (2x^3y^2)(3 + 4xy -5x^2y).

Factoring by grouping[edit]

A method that is sometimes useful, but not guaranteed to work, is factoring by grouping.

Factoring by grouping is done by placing the terms in the polynomial into two or more groups, where each group can be factored by a known method. The results of these partial factorizations can sometimes be combined to give a factorization of the original expression.

For example, to factor the polynomial

4x^2+20x+3yx+15y \,:
  1. group similar terms, (4x^2+20x)+(3yx+15y),\,
  2. factor out the highest common factor in each grouping, 4x(x+5)+3y(x+5),\,
  3. again factor out the binomial common factor, (x+5)(4x+3y).\,

While grouping may not lead to a factorization in general, if the polynomial expression to be factored consists of four terms and is the result of multiplying two binomial expressions (by the FOIL method for instance), then the grouping technique can lead to a factorization, as in the above example.

Using the factor theorem[edit]

Main article: Factor theorem

For a univariate polynomial, p(x), the factor theorem states that a is a root of the polynomial (that is, p(a) = 0, also called a zero of the polynomial) if and only if (x - a) is a factor of p(x). The other factor in such a factorization of p(x) can be obtained by polynomial long division or synthetic division.

For example, consider the polynomial x^3 - 3x + 2. By inspection we see that 1 is a root of this polynomial (observe that the coefficients add up to 0), so (x - 1) is a factor of the polynomial. By long division we have x^3 - 3x + 2 = (x - 1)(x^2 + x - 2).

Univariate case, using properties of the roots[edit]

When a univariate polynomial is completely factored into linear factors (degree one factors), all of the roots of the polynomial are visible and by multiplying the factors together again, the relationship between the roots and the coefficients can be observed. Formally, these relationships are known as Vieta's formulas. These formulas do not help in factorizing the polynomial except as a guide to making good guesses at what possible roots may be. However, if some additional information about the roots is known, this can be combined with the formulas to obtain the roots and thus the factorization.

For example,[6] we can factor x^3 -5x^2 -16x +80 if we know that the sum of two of its roots is zero. Let r_1, r_2 and r_3 be the three roots of this polynomial. Then Vieta's formulas are:


 \begin{align}
    r_1 + r_2 + r_3 &= 5 \\
    r_1r_2 +r_2r_3 + r_3r_1 &= -16 \\
     r_1r_2r_3 &= -80.
  \end{align}

Assuming that r_2 + r_3 = 0 immediately gives r_1= 5 and reduces the other two equations to r_2^2 = 16. Thus the roots are 5, 4 and -4 and we have x^3 - 5x^2 - 16x + 80 = (x -5)(x-4)(x+4).

Finding rational roots[edit]

If a (univariate) polynomial, f(x), has a rational root, p/q (p and q are integers and q ≠ 0), then by the factor theorem f(x) has the factor,

(x - \frac{p}{q}) = \frac{1}{q}(qx - p).

If, in addition, the polynomial f(x) has integer coefficients, then q must evenly divide the integer portion of the highest common factor of the terms of the polynomial, and, in the factorization of f(x), only the factor (qx - p) will be visible.

If a (univariate) polynomial with integer coefficients, say,

 a_0x^n + a_1x^{n-1} + \ldots + a_{n-1}x + a_n

has a rational root p/q, where p and q are integers that are relatively prime, then p is an integer divisor of an and q is an integer divisor of a0.[7]

If we wished to factorize the polynomial 2x^3 - 7x^2 + 10x - 6 we could look for rational roots p/q where p divides -6, q divides 2 and p and q have no common factor greater than 1. By inspection we see that this polynomial can have no negative roots. Assume that q = 2 (otherwise we would be looking for integer roots), substitute x = p/2 and set the polynomial equal to 0. By dividing by 4, we obtain the polynomial equation p^3 - 7p^2 + 20p -24 = 0 that will have an integer solution of 1 or 3 if the original polynomial had a rational root of the type we seek. Since 3 is a solution of this equation (and 1 is not), the original polynomial had the rational root 3/2 and the corresponding factor (2x - 3). By polynomial long division we have the factorization 2x^3 - 7x^2 + 10x - 6 = (2x -3)(x^2 -2x + 2).

For a quadratic polynomial with integer coefficients having rational roots, the above considerations lead to a factorization technique known as the ac method of factorization.[8] Suppose that the quadratic polynomial with integer coefficients is:

ax^2 + bx + c

and it has rational roots, p/q and u/v. (If the discriminant, b^2 - 4ac, is a square number these exist, otherwise we have irrational or complex solutions, and there will be no rational roots.) Both q and v must be divisors of a so we may write these fractions with a common denominator of a, that is, they may be written as -r/a and -s/a (the use of the negatives is cosmetic and leads to a prettier final result.) Then,


ax^2 + bx + c  = a(x^2 + \frac{b}{a}x + \frac{c}{a})  = a(\frac{1}{a}(ax+r)\frac{1}{a}(ax+s)) = \frac{(ax+r)(ax+s)}{a}.

So, we have:

a^2x^2 + abx +ac = (ax+r)(ax+s),

where rs = ac and r + s = b. The ac method for factoring the quadratic polynomial is to find r and s, the two factors of the number ac whose sum is b and then use them in the factorization formula of the original quadratic above.

As an example consider the quadratic polynomial:

6x^2 + 13x + 6.

Inspection of the factors of ac = 36 leads to 4 + 9 = 13 = b.


\begin{align}
6x^2 + 13x + 6 & = \frac{(6x+4)(6x+9)}{6} \\
&= \frac{2(3x+2)(3)(2x+3)}{6} \\
&= (3x+2)(2x+3)
\end{align}

Recognizable patterns[edit]

While taking the product of two (or more) expressions can be done by following a multiplication algorithm, the reverse process of factoring relies frequently on the recognition of a pattern in the expression to be factored and recalling how such a pattern arises. The following are some well known patterns.[9]

Difference of two squares[edit]

A common type of algebraic factoring is called the difference of two squares. It is the application of the formula

 a^2 - b^2 = (a+b)(a-b),\,\!

to any two terms, whether or not they are perfect squares.

This basic form is often used with more complicated expressions that may not a first look like the difference of two squares. For example,

\begin{align}
a^2 + 2ab + b^2 - x^2 +2xy - y^2 &= (a^2 + 2ab + b^2) - (x^2 -2xy + y^2) \\
&= (a+b)^2 - (x -y)^2 \\
&= (a+b + x -y)(a+b -x + y).
\end{align}

Sum/difference of two cubes[edit]

A visual representation of the factorization of cubes using volumes. For a sum of cubes, simply substitute z=-y.

Another formula for factoring is the sum or difference of two cubes. The sum can be factored by

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

and the difference by

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

Difference of two fourth powers[edit]

Another formula is the difference of two fourth powers, which is

 a^4 - b^4 = (a^2 + b^2)(a^2 - b^2) = (a^2 + b^2)(a + b)(a - b).\,\!

Sum/difference of two nth powers[edit]

The above factorizations of differences or sums of powers can be extended to any positive integer power n.

For any n, a general factorization is:

 a^n - b^n  = (a-b)(a^{n-1} + ba^{n-2} + b^2 a^{n-3} + \ldots + b^{n-2} a + b^{n-1} ).\!

The corresponding formula for the sum of two nth powers depends on whether n is even or odd. If n is odd, b can be replaced by −b in the above formula, to give

 a^n + b^n  = (a+b)(a^{n-1} - ba^{n-2} + b^2 a^{n-3} - \ldots - b^{n-2} a + b^{n-1} ).\!

If n is even, we consider two cases:

1. If n is a power of 2 then  a^n + b^n\! is unfactorable (more precisely, irreducible over the rational numbers).

2. Otherwise,  n = m \cdot 2^k, m>1, k > 0 where m is odd. In this case we have,

 a^n + b^n  = (a^{2^k} + b^{2^k})(a^{n-2^k} - a^{n-2 \cdot 2^k} b^{2^k}  + a^{n-3 \cdot 2^k} b^{2 \cdot 2^k} - \ldots - a^{2^k} b^{n-2 \cdot 2^k} + b^{n-2^k}) = (a^{2^k} + b^{2^k}) \sum_{i=1}^m a^{(m-i)2^k}(-b^{2^k})^{i-1}.\!

Specifically, for some small values of n we have:

 a^5 + b^5 = (a + b)(a^4 - a^3 b + a^2 b^2 - a b^3 + b^4),\,\!
 a^5 - b^5 = (a - b)(a^4 + a^3 b + a^2 b^2 + a b^3 + b^4).\,\!
 a^6 + b^6 = (a^2 + b^2)(a^4 - a^2 b^2 + b^4),\,\!
 a^6 - b^6 = (a^3 + b^3)(a^3 - b^3) = (a + b)(a - b)(a^2 - ab + b^2)(a^2 + ab + b^2).\,\!
 a^7 + b^7 = (a + b) (a^6 - a^5 b + a^4 b^2 - a^3 b^3 + a^2 b^4 - a b^5 + b^6),\,\!
 a^7 - b^7 = (a - b)(a^6 + a^5 b + a^4 b^2 + a^3 b^3 + a^2 b^4 + a b^5 + b^6).\,\!

Binomial expansions[edit]

A visual illustration of the identity (a + b)2 = a2 + 2ab + b2

The binomial theorem supplies patterns of coefficients that permit easily recognized factorizations when the polynomial is a power of a binomial expression.

For example, the perfect square trinomials are the quadratic polynomials that can be factored as follows:

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

and

 a^2 - 2ab + b^2 = (a - b)^2.\,\!

Some cubic polynomials are four term perfect cubes that can be factored as:

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

and

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

In general, the coefficients of the expanded polynomial (a+b)^n are given by the n-th row of Pascal's triangle. The coefficients of (a-b)^n have the same absolute value but alternate in sign.

Other factorization formulae[edit]


\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^4 + x^2y^2 + y^4 \,& = (x^2 + xy+y^2)(x^2 - xy + y^2).
\end{align}

Using formulas[edit]

Any quadratic polynomial (polynomials of the form ax^2+bx+c) can be factored using the quadratic formula, as follows:


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, found with the quadratic formula.

The quadratic formula is valid for all polynomials with coefficients in any field (in particular, the real or complex numbers) except those that have characteristic two.[10]

There are also formulas for cubic and quartic polynomials which can be used in the same way. However, there are no formulas in terms of the coefficients that exist for higher degree (univariate) polynomials by the Abel-Ruffini theorem.

Factoring over the complex numbers[edit]

Sum of two squares[edit]

If a and b represent real numbers, then the sum of their squares can be written as the product of complex numbers. This produces the factorization formula:

 a^2 + b^2 = (a+bi)(a-bi). \,\!

For example, 4x^2 + 49 can be factored into (2x + 7i)(2x - 7i).

Sum/difference of two nth powers over the field of the algebraic numbers[edit]

A thorough factorization can be obtained over the field of the algebraic numbers, as showed by the following reduction formulae, which are proved going through the complex conjugate roots of  f(a) = a^n \pm b^n.

The sum of two even powers is factored by

 a^{2n} + \ b^{2n} = \prod_{k=1}^n \Bigl(a^2 \ \pm \ 2ab\cos\frac{(2k-1)\pi}{2n} \ + \ b^2\Bigl).\!

The difference of two even powers is factored by

 a^{2n} - \ b^{2n} = (a\ -\ b)(a\ +\ b)\prod_{k=1}^{n-1} \Bigl(a^2 \ \pm \ 2ab\cos\frac{k\pi}n \ + \ b^2\Bigl).\!

The sum or difference of two odd powers is factored by

 a^{2n+1}\ \pm \ b^{2n+1} = (a\ \pm\ b)\prod_{k=1}^n \Bigl(a^2\  \pm\ 2ab\cos\frac{2k\pi}{2n+1}\ +\ b^2\Bigl) = (a\ \pm\ b)\prod_{k=1}^n \Bigl(a^2\ \pm\ 2ab(-1)^k\cos\frac{k\pi}{2n+1}\ +\ b^2\Bigl).\!

For instance, the sum or difference of two fifth powers is factored by

 a^5 \pm b^5 = (a \pm b)\Biggl(a^2 \mp\frac{1-\sqrt 5}2 ab + b^2\Biggl)\Biggl(a^2 \mp\frac{1+\sqrt 5}2 ab + b^2\Biggl).\!

and the sum of two fourth powers is factored by

 a^4 + b^4 = (a^2 - \sqrt 2 ab + b^2)(a^2 + \sqrt 2 ab + b^2).\!

Matrices[edit]

Main article: Matrix decomposition

Unique factorization domains[edit]

Euclidean domains[edit]

Main article: Euclidean domain

See also[edit]

Notes[edit]

  1. ^ Hardy; Wright (1980). An Introduction to the Theory of Numbers (5th ed.). Oxford Science Publications. ISBN 978-0198531715. 
  2. ^ Fite 1921, p. 20
  3. ^ Even if the 3 is thought of as a constant polynomial so that this could be considered a factorization into polynomials.
  4. ^ Klein 1925, pp. 101-102
  5. ^ Fite 1921, p. 19
  6. ^ Burnside & Panton 1960, p. 38
  7. ^ Dickson 1922, p. 27
  8. ^ Stover, Christopher AC Method - Mathworld
  9. ^ Selby 1970, p. 101
  10. ^ In these fields 2 = 0 so the division in the formula is not valid. There are other ways to find roots of quadratic equations over these fields.

References[edit]

  • Burnside, William Snow; Panton, Arthur William (1960) [1912], The Theory of Equations with an introduction to the theory of binary algebraic forms (Volume one), Dover 
  • Dickson, Leonard Eugene (1922), First Course in the Theory of Equations, New York: John Wiley & Sons 
  • Fite, William Benjamin (1921), College Algebra (Revised), Boston: D. C. Heath & Co. 
  • Klein, Felix (1925), Elementary Mathematics from an Advanced Standpoint; Arithmetic, Algebra, Analysis, Dover 
  • Selby, Samuel M., CRC Standard Mathematical Tables (18th ed.), The Chemical Rubber Co. 

External links[edit]