Factorization
In mathematics, factorization 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, is an integer factorization of, and is a polynomial factorization of.
Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any can be trivially written as whenever 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 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 factorizations within the ring of polynomials with rational number coefficients.
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 with all diagonal entries equal to one, an upper triangular matrix, and a permutation matrix ; this is a matrix formulation of Gaussian elimination.
Integers
By the fundamental theorem of arithmetic, every integer greater than 1 has a unique 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, one needs an algorithm for finding a divisor of or deciding that is prime. When such a divisor is found, the repeated application of this algorithm to the factors and gives eventually the complete factorization of.
For finding a divisor of, if any, it suffices to test all values of such that and. In fact, if is a divisor of such that, then is a divisor of such that.
If one tests the values of in increasing order, the first divisor that is found is necessarily a prime number, and the cofactor cannot have any divisor smaller than. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of that is not smaller than and not greater than.
There is no need to test all values of 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
is not a prime number. In fact, applying the above method would require more than, 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 ensures the security of the RSA cryptosystem, which is widely used for secure internet communication.
Example
For factoring into primes:- Start with division by 2: the number is even, and. Continue with 693, and 2 as a first divisor candidate.
- 693 is odd, but is a multiple of 3: one has and. Continue with 231, and 3 as a first divisor candidate.
- 231 is also a multiple of 3: one has, and thus. 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, and thus. This shows that 7 is prime. Continue with 11, and 7 as a first divisor candidate.
- As, one has finished. Thus 11 is prime, and the prime factorization is
Expressions
having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression
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, can be factored into two irreducible factors and.
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 of degree with complex coefficients may be factorized into linear factors for, where the s are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the
s generally cannot be computed in terms of radicals, 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 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, and showed that this matches the form of multiplication he had previously provided, giving the factorization .
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,
since 2 is the greatest common divisor of 6, 8, and 10, and divides all terms.
Grouping
Grouping terms may allow using other methods for getting a factorization.For example, to factor
one may remark that the first two terms have a common factor, and the last two terms have the common factor. Thus
Then a simple inspection shows the common factor, leading to the factorization
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 If one introduces the non-real square root of –1, commonly denoted, then one has a difference of squares
However, one may also want a factorization with real number coefficients. By adding and subtracting and grouping three terms together, one may recognize the square of a binomial:
Subtracting and adding also yields the factorization:
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 which is irreducible over the integers, is reducible modulo every prime number. For example,
since
since
since