Factorization is not usually considered meaningful within number systems possessingdivision, such as thereal orcomplex numbers, since any can be trivially written as whenever is not zero. However, a meaningful factorization for arational number or arational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator.
By thefundamental theorem of arithmetic, everyinteger greater than 1 has a unique (up to the order of the factors) factorization intoprime numbers, which are those integers which cannot be further factorized into the product of integers greater than one.
For computing the factorization of an integern, one needs analgorithm for finding adivisorq ofn or deciding thatn is prime. When such a divisor is found, the repeated application of this algorithm to the factorsq andn /q gives eventually the complete factorization ofn.[1]
For finding a divisorq ofn, if any, it suffices to test all values ofq such that1 <q andq2 ≤n. In fact, ifr is a divisor ofn such thatr2 >n, thenq =n /r is a divisor ofn such thatq2 ≤n.
If one tests the values ofq in increasing order, the first divisor that is found is necessarily a prime number, and thecofactorr =n /q cannot have any divisor smaller thanq. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor ofr that is not smaller thanq and not greater than√r.
There is no need to test all values ofq 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 thesieve 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 6thFermat number
is not a prime number. In fact, applying the above method would require more than10000 divisions, 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 theRSA cryptosystem, which is widely used for secureinternet communication.
Start with division by 2: the number is even, andn = 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 has693 = 3 · 231 andn = 2 · 3 · 231. Continue with 231, and 3 as a first divisor candidate.
231 is also a multiple of 3: one has231 = 3 · 77, and thusn = 2 · 32 · 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 has77 = 7 · 11, and thusn = 2 · 32 · 7 · 11. This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate.
As72 > 11, one has finished. Thus 11 is prime, and the prime factorization is
Manipulatingexpressions is the basis ofalgebra. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put anequation in a factored formE⋅F = 0, then the problem of solving the equation splits into two independent (and generally easier) problemsE = 0 andF = 0. When an expression can be factored, the factors are often much simpler, and may thus offer some insight on the problem. For example,
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 givesrootsx =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 twoirreducible factors and.
Various methods have been developed for finding factorizations; some are describedbelow.
However, even for solvingquadratic equations, the factoring method was not used beforeHarriot's work published in 1631, ten years after his death.[3] In his bookArtis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, Harriot drew tables for addition,subtraction, multiplication and division ofmonomials,binomials, andtrinomials. Then, in a second section, he set up the equationaa −ba +ca = +bc, and showed that this matches the form of multiplication he had previously provided, giving the factorization(a −b)(a +c).[4]
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 topolynomials, though they also may be applied when the terms of the sum are notmonomials, that is, the terms of the sum are a product of variables and constants.
It may occur that all terms of a sum are products and that some factors are common to all terms. In this case, thedistributive 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 thegreatest common divisor of these coefficients.
For example,[5]since 2 is the greatest common divisor of 6, 8, and 10, and divides all terms.
Grouping terms may allow using other methods for getting a factorization.
For example, to factorone may remark that the first two terms have a common factorx, and the last two terms have the common factory. ThusThen a simple inspection shows the common factorx + 5, leading to the factorization
In general, this works for sums of 4 terms that have been obtained as the product of twobinomials. Although not frequently, this may work also for more complicated examples.
Another example is the factorization of If one introduces the non-realsquare root of –1, commonly denotedi, then one has adifference of squaresHowever, one may also want a factorization withreal number coefficients. By adding and subtracting and grouping three terms together, one may recognize the square of abinomial:Subtracting and adding also yields the factorization:These factorizations work not only over the complex numbers, but also over anyfield, where either –1, 2 or –2 is a square. In afinite field, the product of two non-squares is a square; this implies that thepolynomial which isirreducible over the integers, is reduciblemodulo everyprime number. For example,sincesincesince
Manyidentities 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 variablesE andF that appear in these identities may represent any subexpression of the expression that has to be factorized).[6]
Visual proof of the differences between two squares and two cubes
In the following identities, the factors may often be further factorized:
Difference, even exponent
Difference, even or odd exponent
This is an example showing that the factors may be much larger than the sum that is factorized.
Sum, odd exponent
(obtained by changingF by–F in the preceding formula)
Sum, even exponent
If the exponent is apower of two then the expression cannot, in general, be factorized without introducingcomplex numbers (ifE andF contain complex numbers, this may be not the case). Ifn has an odd divisor, that is ifn =pq withp odd, one may use the preceding formula (in "Sum, odd exponent") applied to
It follows that for any two expressionsE andF, one has:
IfE andF are real expressions, and one wants real factors, one has to replace every pair ofcomplex conjugate factors by its product. As the complex conjugate of is andone has the following real factorizations (one passes from one to the other by changingk inton −k orn + 1 −k, and applying the usualtrigonometric formulas:
Thecosines that appear in these factorizations arealgebraic numbers, and may be expressed in terms ofradicals (this is possible because theirGalois group is cyclic); however, these radical expressions are too complicated to be used, except for low values ofn. For example,
Often one wants a factorization with rational coefficients. Such a factorization involvescyclotomic polynomials. To express rational factorizations of sums and differences or powers, we need a notation for thehomogenization of a polynomial: if itshomogenization is thebivariate polynomial Then, one haswhere the products are taken over all divisors ofn, or all divisors of2n that do not dividen, and is thenth cyclotomic polynomial.
For example,since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.
For polynomials, factorization is strongly related with the problem of solvingalgebraic equations. An algebraic equation has the form
whereP(x) is a polynomial inx withA solution of this equation (also called aroot of the polynomial) is a valuer ofx such that
If is a factorization ofP(x) = 0 as a product of two polynomials, then the roots ofP(x) are theunion of the roots ofQ(x) and the roots ofR(x). Thus solvingP(x) = 0 is reduced to the simpler problems of solvingQ(x) = 0 andR(x) = 0.
Conversely, thefactor theorem asserts that, ifr is a root ofP(x) = 0, thenP(x) may be factored as
whereQ(x) is the quotient ofEuclidean division ofP(x) = 0 by the linear (degree one) factorx −r.
If the coefficients ofP(x) arereal orcomplex numbers, thefundamental theorem of algebra asserts thatP(x) has a real or complex root. Using the factor theorem recursively, it results that
where are the real or complex roots ofP, with some of them possibly repeated. This complete factorization is uniqueup to the order of the factors.
If the coefficients ofP(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, ifr =a +ib is a non-real root ofP(x), then itscomplex conjugates =a −ib is also a root ofP(x). So, the product
is a factor ofP(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 usingroot-finding algorithms.
In practice, most algebraic equations of interest haveinteger orrational coefficients, and one may want a factorization with factors of the same kind. Thefundamental theorem of arithmetic may be generalized to this case, stating that polynomials with integer or rational coefficients have theunique factorization property. More precisely, every polynomial with rational coefficients may be factorized in a product
whereq is a rational number and are non-constant polynomials with integer coefficients that areirreducible andprimitive; this means that none of the 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 efficientalgorithms for computing this factorization, which are implemented in mostcomputer algebra systems. SeeFactorization 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.
Every polynomial withrational coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which isprimitive (that is, thegreatest common divisor of the coefficients is 1), and has a positive leading coefficient (coefficient of the term of the highest degree). For example:
In this factorization, the rational number is called thecontent, and the primitive polynomial is theprimitive 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 integerq of a polynomial with integer coefficients. Then one divides out the greater common divisorp of the coefficients of this polynomial for getting the primitive part, the content being Finally, if needed, one changes the signs ofp and all coefficients of the primitive part.
This factorization may produce a result that is larger than the original polynomial (typically when there are manycoprime denominators), but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.
For polynomials with rational number coefficients, one may search for roots which are rational numbers. Primitive part-content factorization (seeabove) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivialcommon divisor.
If is a rational root of such a polynomial
the factor theorem shows that one has a factorization
where both factors have integer coefficients (the fact thatQ has integer coefficients results from the above formula for the quotient ofP(x) by).
Comparing the coefficients of degreen and the constant coefficients in the above equality shows that, if is a rational root inreduced form, thenq is a divisor of andp is a divisor of Therefore, there is a finite number of possibilities forp andq, which can be systematically examined.[7]
For example, if the polynomial
has a rational root withq > 0, thenp must divide 6; that is andq must divide 2, that is Moreover, ifx < 0, all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have
A direct computation shows that only is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization
The above method may be adapted forquadratic polynomials, leading to theac method of factorization.[8]
Consider the quadratic polynomial
with integer coefficients. If it has a rational root, its denominator must dividea evenly and it may be written as a possiblyreducible fraction ByVieta's formulas, the other root is
withThus the second root is also rational, and Vieta's second formula gives
that is
Checking all pairs of integers whose product isac gives the rational roots, if any.
In summary, if has rational roots there are integersr ands such and (a finite number of cases to test), and the roots are and In other words, one has the factorization
For example, let consider the quadratic polynomial
Inspection of the factors ofac = 36 leads to4 + 9 = 13 =b, giving the two roots
Ifa, b, c are allreal, the factors are realif and only if thediscriminant 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 anyfield ofcharacteristic different from two, and, in particular, for coefficients in afinite field with an odd number of elements.[9]
There are also formulas for roots ofcubic andquartic polynomials, which are, in general, too complicated for practical use. TheAbel–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 includeVieta's formulas.
Here, we consider the simpler case where two rootsand of a polynomial satisfy the relation
whereQ is a polynomial.
This implies that is a common root of and It is therefore a root of thegreatest common divisor of these two polynomials. It follows that this greatest common divisor is a non constant factor ofEuclidean algorithm for polynomials allows computing this greatest common factor.
For example,[10] if one know or guess that: has two roots that sum to zero, one may apply Euclidean algorithm to and The first division step consists in adding to giving theremainder of
Then, dividing by gives zero as a new remainder, andx − 5 as a quotient, leading to the complete factorization
The integers and the polynomials over afield share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (aunit, ±1 in the case of integers) and a product ofirreducible 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 calledunique factorization domains (UFD).
AEuclidean domain is an integral domain on which is defined aEuclidean 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 aEuclidean algorithm for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of afieldF such that there cannot exist any factorization algorithm in the Euclidean domainF[x] of the univariate polynomials overF.
Unfortunately, it soon appeared that most rings of algebraic integers are not principal and do not have unique factorization. The simplest example is in which
This lack of unique factorization is a major difficulty for solving Diophantine equations. For example, many wrong proofs ofFermat's Last Theorem (probably includingFermat'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 byDedekind, who proved that the rings of algebraic integers have unique factorization ofideals: in these rings, every ideal is a product ofprime ideals, and this factorization is unique up the order of the factors. Theintegral domains that have this unique factorization property are now calledDedekind domains. They have many nice properties that make them fundamental in algebraic number theory.
Matrix rings are non-commutative and have no unique factorization: there are, in general, many ways of writing amatrix as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, theLU decomposition gives a matrix as the product of alower triangular matrix by anupper triangular matrix. As this is not always possible, one generally considers the "LUP decomposition" having apermutation matrix as its third factor.
^InSanford, Vera (2008) [1930],A Short History of Mathematics, Read Books,ISBN9781409727101, the author notes "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".
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
