In mathematics, factorization (also factorisation in some forms of British English) or factoring consists of writing a number or another mathematical object as a product of several factors. For example, 3 × 5 is a factorization of the integer 15, and (x – 2)(x + 2) is a factorization of the polynomial x2 – 4.
Factorization has been considered first by ancient Greek mathematicians, in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factorized into a product of specific integers called prime numbers, that have the property of not having any factorization in factors different of one. Moreover, this factorization is unique up to the order of the factors. Factorization is, somehow, the inverse operation of multiplication. However, in the case of large integers, integer factorization is much more difficult than multiplication, and this is widely used in public-key cryptography, typically through the RSA cryptosystem.
Polynomial factorization is also considered since a long time. Polynomials with integer coefficients or coefficients in a field have the unique factorization property, that is verify a theorem that is very similar to 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 the order of the factors) factorization into linear polynomials; this is the fundamental theorem of algebra. In this case, the factorization is usually done with root-finding algorithms. The case of polynomials with integer coefficients is fundamental for computer algebra. There are algorithms for computing the (complete) factorization of any polynomial with integer coefficients (see factorization of polynomials); although they are very efficient for a computer usage, they are generally too complicate for being used in paper-and-pencil computation.
The commutative rings in which unique factorization property holds are called unique factorization domains. There are number systems which are not unique factorization domains. This is the case of many rings of algebraic integers. However, these are Dedekind domains, which means that unique factorization property holds if one replaces factorization into algebraic integers by factorization into ideals.
Factorization is often used for the decomposition of a mathematical object into the product of objects of a more specific type. For example every function may be factored into the composition of a surjective function with an injective function. For matrices, there are many kinds of such matrix factorizations. For example, every matrix has a LUP factorization as a product of a square lower triangular matrix L with all diagonal entries equal to one, an upper triangular matrix U, and a permutation matrix P.
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 q2 ≤ n. In fact, if r is a divisor of n such that r2 > n, then q = n / r is a divisor of n such that q2 ≤ 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 √.
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.
is not a prime number. In fact, applying the above method would require more than 10,000 division, for a number that has 10 decimal digits.
There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This insure the security of the RSA cryptosystem, which is widely used for secure communications on Internet.
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 · 32 · 77. Continue with 77, and 3 as a first divisor candidate.
- 77 is not a multiple 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 · 32 · 7 · 11. This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate.
- As 72 > 11, one has finished. Thus 11 is prime, and the prime factorization is
- 1386 = 2 · 32 · 7 · 11.
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; these hand techniques 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 is a factorization of the expression, it is not a polynomial factorization since the factors are not polynomials. Also, the factoring of a constant term, as in would not be considered a polynomial factorization since one of the factors does not have a smaller degree than the original expression. 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 then 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. .
The fundamental theorem of algebra can be stated as: Every polynomial of degree n with complex number coefficients splits completely into n linear factors. The terms in these factors, which are the roots of the polynomial, may be real or complex. Since complex roots of polynomials with real coefficients come in complex conjugate pairs, this result implies that every polynomial with real coefficients splits into linear and/or irreducible quadratic factors with real coefficients (because when two linear factors with complex conjugate terms are multiplied together, the result is a quadratic with real coefficients). Even though the structure of the factorization is known in these cases, finding the actual factors can be computationally challenging, and by the Abel–Ruffini theorem the coefficients and additive terms in the factors may not be expressible in terms of radicals.
History of factoring polynomialsEdit
Students who are introduced to factoring as a primary method of solving quadratic equations might be surprised to know it is one of the newest methods of solving them. Vera Sanford points out in her A Short History of Mathematics (1930) that “In view of the present emphasis given to the solution of quadratic equations by factoring, it is interesting to note that this method was not used until Harriot’s work of 1631. Even in this case, however, the author ignores the factors that give rise to negative roots.” Harriot died in 1621, and like all his books, this one, Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, was published after his death. An article on Harriot at the Univ of Saint Andrews math history web site says that in his personal writing on solving equations Harriot did use both positive and negative solutions, but his editor, Walter Warner, did not present this in his book. Harriot’s method of factoring may look different than what modern students expect. In the first section (Sectio Prima) Harriot draws tables to illustrate the addition, subtraction, multiplication and division of monomial, binomial, and trinomial terms. Then in the second section he shows a more direct multiplication that provides the foundation to his factoring method. He sets up the equation aa − ba + ca = + bc, and shows that this matches the form of multiplication he has previously provided as,
a − b aa − ba (===) (Harriot uses the long equal sign introduced by Robert Recorde) a + c ca − bc
thus factoring the four terms of the adjusted expression aa − ba + ca − bc. This example can be seen on page 16 of the Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas.
Harriot writes out a form for each of the possibilities of (a ± b)(a ± c) with a being the unknown (where we might use x today) and then when he needs to factor he picks on one of the forms that match. By separating out the linear coefficient into two parts he is able to break the problem into one of the forms.
There are general algorithms which always produce the complete factorization of any polynomial, in either one variable (the univariate case) or several variables (the multivariate case); see Factorization of polynomials. These algorithms are implemented and are available in most computer algebra systems. They involve advanced properties of polynomials, and are too complicated for hand-written computation. There are also a few elementary methods which are well–suited for hand-written computation, and do not always allow finding the complete factorization in degree higher than four.
Highest common factorEdit
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:
Factoring by groupingEdit
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
- group similar terms,
- factor out the highest common factor in each grouping,
- again factor out the binomial common factor,
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 theoremEdit
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 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
Univariate case, using the properties of rootsEdit
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 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, we can factor if we know that the sum of two of its roots is zero. Let and be the three roots of this polynomial. Then Vieta's formulas are:
Assuming that immediately gives and reduces the other two equations to Thus the roots are 5, 4 and –4 and we have
Finding rational rootsEdit
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,
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,
If we wished to factorize the polynomial 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 multiplying by 4, we obtain the polynomial equation 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
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. Suppose that the quadratic polynomial with integer coefficients is:
and it has rational roots, p/q and u/v. (If the discriminant, , 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,
So, we have:
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:
Inspection of the factors of ac = 36 leads to 4 + 9 = 13 = b.
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.
Difference of two squaresEdit
A common type of algebraic factoring is for the difference of two squares. It is the application of the formula
to any two terms, whether or not they are perfect squares.
This basic form is often used with more complicated expressions that may not at first look like the difference of two squares. For example,
Sum/difference of two cubesEdit
Another formula for factoring is for the sum or difference of two cubes. The sum can be factored by
and the difference by
Difference of two fourth powersEdit
Two formulas for factoring the difference of two fourth powers are as follows:
Sum/difference of two nth powersEdit
- Difference, even n
The above factorizations of differences or sums of powers can be extended to any positive integer power n.
For even n, we have
The first parenthetical term, and possibly the second one, can be further factored using the following formulas.
- Difference, even or odd n
For any n, a general factorization is:
- Sum, odd n
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
- Sum, even n
If n is even, we consider two cases:
- If n is a power of 2 then is unfactorable (more precisely, irreducible over the rational numbers).
- Otherwise, where m is odd. In this case we have,
Specifically, for some small values of n we have:
Sum/difference of two nth powers over the field of the real algebraic numbersEdit
The above factorizations give factors with coefficients in the same field as those of the expression being factored—for example, a polynomial with rational coefficients (±1 in many cases above) is split into factors which themselves have rational coefficients. However, a factorization into factors with algebraic numbers (numbers that are the solution of some polynomial equation) as coefficients can yield lower-degree factors, as in the following formulas which can be proven by going through the complex conjugate roots of (The cosine expressions are algebraic numbers because they are trigonometric numbers.)
The sum of two terms that have equal even powers is factored by
The difference of two terms that have equal even powers is factored by
The sum or difference of two terms that have equal odd powers is factored by
For instance, the sum or difference of two fifth powers is factored by
and the sum of two fourth powers is factored by
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:
Some cubic polynomials are four term perfect cubes that can be factored as:
In general, the coefficients of the expanded polynomial are given by the n-th row of Pascal's triangle. The coefficients of have the same absolute value but alternate in sign.
Other factorization formulasEdit
Using formulas for polynomial rootsEdit
There are also formulas for cubic and quartic polynomials which can be used in the same way. However, there are no algebraic formulas in terms of the coefficients that apply to all univariate polynomials of a higher degree, by the Abel–Ruffini theorem.
Factoring over the complex numbersEdit
Sum of two squaresEdit
For example, can be factored into .
This section needs expansion with: a summary of the linked article. You can help by adding to it. (September 2017)
Unique factorization domainsEdit
This section needs expansion with: with an explanation that unique factorization domains are a formalization of the general problem of factorization. You can help by adding to it. (September 2017)
This section needs expansion with: an explanation on the relationship of the linked article, with the subject of this article. You can help by adding to it. (September 2017)
- Completing the square for polynomials
- Euler's factorization method for integers
- Fermat's factorization method for integers
- Integer factorization
- Monoid factorisation
- Multiplicative partition
- Partition (number theory) – a way of writing a number as a sum of positive integers
- Prime factor
- Program synthesis
- Table of Gaussian integer factorizations
- Hardy; Wright (1980). An Introduction to the Theory of Numbers (5th ed.). Oxford Science Publications. ISBN 978-0198531715.
- Fite 1921, p. 20
- Even if the 3 is thought of as a constant polynomial so that this could be considered a factorization into polynomials.
- Klein 1925, pp. 101–102
- Sanford, Vera (2008) , A Short History of Mathematics, Read Books, ISBN 9781409727101
- Fite 1921, p. 19
- Burnside & Panton 1960, p. 38
- Dickson 1922, p. 27
- Stover, Christopher AC Method - Mathworld
- Selby 1970, p. 101
- 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.
- Burnside, William Snow; Panton, Arthur William (1960) , 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.
|Look up factorisation or factorization in Wiktionary, the free dictionary.|
- Hazewinkel, Michiel, ed. (2001) , "Factorization of polynomials", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- One hundred million numbers factored on html pages.
- WIMS Factoris is an online factorization tool.
- Wolfram Alpha can factorize too.