Editing Factorization

{{Short description|(Mathematical) decomposition into a product}}
{{other uses|Factor (disambiguation)}}
[[File:Factorisatie.svg|thumb|right|The polynomial ''x''<sup>2</sup>&nbsp;+&nbsp;''cx''&nbsp;+&nbsp;''d'', where ''a&nbsp;+&nbsp;b&nbsp;=&nbsp;c'' and ''ab&nbsp;=&nbsp;d'', can be factorized into (''x&nbsp;+&nbsp;a'')(''x&nbsp;+&nbsp;b'').]]

In [[mathematics]], '''factorization''' (or '''factorisation''', see [[American and British English spelling differences#-ise, -ize (-isation, -ization)|English spelling differences]]) or '''factoring''' consists of writing a number or another [[mathematical object]] as a product of several ''[[Factor (arithmetic)|factors]]'', usually smaller or simpler objects of the same kind. For example, {{math|3 × 5}} is an ''[[integer factorization]]'' of {{math|15}}, and {{math|(''x'' − 2)(''x'' + 2)}} is a ''[[polynomial factorization]]'' of {{math|''x''<sup>2</sup> − 4}}.

Factorization is not usually considered meaningful within number systems possessing [[division ring|division]], such as the [[real number|real]] or [[complex number]]s, since any <math>x</math> can be trivially written as <math>(xy)\times(1/y)</math> whenever <math>y</math> 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 [[Greek mathematics|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 number]]s, 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 [[Integer factorization|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 [[Zero of a function|roots]] to finding the roots of the factors. Polynomials with coefficients in the integers or in a [[field (mathematics)|field]] possess the [[unique factorization domain|unique factorization property]], a version of the fundamental theorem of arithmetic with prime numbers replaced by [[irreducible polynomial]]s. In particular, a [[univariate polynomial]] with [[complex number|complex]] coefficients admits a unique (up to ordering) factorization into [[linear polynomial]]s: this is a version of the [[fundamental theorem of algebra]]. In this case, the factorization can be done with [[root-finding algorithm]]s. The case of polynomials with integer coefficients is fundamental for [[computer algebra]]. There are efficient computer [[algorithm]]s 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 system]]s, such as certain [[ring of algebraic integers|rings of algebraic integers]], which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of [[Dedekind domain]]s: [[ideal (ring theory)|ideals]] factor uniquely into [[prime ideal]]s.

''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]]. [[matrix (mathematics)|Matrices]] possess many kinds of [[matrix factorization]]s. For example, every matrix has a unique [[LU decomposition|LUP factorization]] as a product of a [[lower triangular matrix]] {{mvar|L}} with all diagonal entries equal to one, an [[upper triangular matrix]] {{mvar|U}}, and a [[permutation matrix]] {{mvar|P}}; this is a matrix formulation of [[Gaussian elimination]].

==Integers==
{{Main|Integer factorization}}

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

For computing the factorization of an integer {{mvar|n}}, one needs an [[algorithm]] for finding a [[divisor]] {{mvar|q}} of {{mvar|n}} or deciding that {{mvar|n}} is prime. When such a divisor is found, the repeated application of this algorithm to the factors {{mvar|q}} and {{math|''n'' / ''q''}} gives eventually the complete factorization of {{mvar|n}}.<ref>{{Cite book |last1=Hardy|last2=Wright |title=An Introduction to the Theory of Numbers |isbn=978-0198531715 |edition=5th |year=1980 |publisher=Oxford Science Publications |url-access=registration |url=https://archive.org/details/introductiontoth00hard|mode=cs2}}</ref>

For finding a divisor {{mvar|q}} of {{mvar|n}}, if any, it suffices to test all values of {{mvar|q}} such that {{math|1 < ''q''}} and {{math|''q''<sup>2</sup> ≤ ''n''}}. In fact, if {{math|''r''}} is a divisor of {{mvar|n}} such that {{math|''r''<sup>2</sup> > ''n''}}, then {{math|1=''q'' = ''n'' / ''r''}} is a divisor of {{mvar|n}} such that {{math|''q''<sup>2</sup> ≤ ''n''}}.

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

There is no need to test all values of {{mvar|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 >&nbsp;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]] 
: <math>1 + 2^{2^5} = 1 + 2^{32} = 4\,294\,967\,297</math>
is not a prime number. In fact, applying the above method would require more than {{val|10,000|u=divisions}}, for a number that has 10&nbsp;[[decimal digit]]s.

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 {{math|1=''n'' = 1386}} into primes:
* Start with division by 2: the number is even, and {{math|1=''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 {{math|1= 693 = 3 · 231}} and {{math|1=''n'' = 2 · 3 · 231}}. Continue with 231, and 3 as a first divisor candidate.
* 231 is also a multiple of 3: one has {{math|1= 231 = 3 · 77}}, and thus {{math|1=''n'' = 2 · 3<sup>2</sup> · 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 {{math|1= 77 = 7 · 11}}, and thus {{math|1=''n'' = 2 · 3<sup>2</sup> · 7 · 11}}. This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate. 
* As {{math|7<sup>2</sup> > 11}}, one has finished. Thus 11 is prime, and the prime factorization is 
: {{math|1=1386 = 2 · 3<sup>2</sup> · 7 · 11}}.

==Expressions==
Manipulating [[expression (mathematics)|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 {{math|1=''E''⋅''F'' = 0}}, then the problem of solving the equation splits into two independent (and generally easier) problems {{math|1=''E'' = 0}} and {{math|1=''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,
:<math>x^3-ax^2-bx^2-cx^2+ abx+acx+bcx-abc</math>
having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression 
:<math>(x-a)(x-b)(x-c),</math> 
with only two multiplications and three subtractions. Moreover, the factored form immediately gives [[zero of a function|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, <math>x^{10}-1</math> can be factored into two [[irreducible polynomial|irreducible factors]] <math>x-1</math> and <math>x^{9}+x^{8}+\cdots+x^2+x+1</math>.

Various methods have been developed for finding factorizations; some are described [[#General methods|below]].

Solving [[algebraic equation]]s may be viewed as a problem of [[polynomial factorization]]. In fact, the [[fundamental theorem of algebra]] can be stated as follows: every [[polynomial]] in {{mvar|x}} of degree {{math|''n''}} with [[complex number|complex]] coefficients may be factorized into {{math|''n''}} linear factors <math>x-a_i,</math> for {{math|1=''i'' = 1, ..., ''n''}}, where the {{math|''a''<sub>''i''</sub>}}s are the roots of the polynomial.<ref>{{harvnb|Klein|1925|pp=101–102}}</ref> Even though the structure of the factorization is known in these cases, the
{{math|''a''<sub>''i''</sub>}}s generally cannot be computed in terms of radicals (''n''<sup>th</sup> roots), by the [[Abel–Ruffini theorem]]. In most cases, the best that can be done is computing [[approximation|approximate value]]s of the roots with a [[root-finding algorithm]].

===History of factorization of expressions===

The systematic use of algebraic manipulations for simplifying expressions (more specifically [[equation]]s) may be dated to 9th century, with [[Muhammad ibn Musa al-Khwarizmi|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 equation]]s, the factoring method was not used before [[Thomas Harriot|Harriot]]'s work published in 1631, ten years after his death.<ref>In {{citation|first=Vera|last=Sanford|title=A Short History of Mathematics|year=2008|orig-year=1930|publisher=Read Books|isbn=9781409727101}}, 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".</ref> In his book ''Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas'', Harriot drew tables for addition, subtraction, multiplication and division of [[monomial]]s, [[binomial (polynomial)|binomial]]s, and [[trinomial]]s. Then, in a second section, he set up the equation {{math|1=''aa'' − ''ba'' + ''ca''  = + ''bc''}}, and showed that this matches the form of multiplication he had previously provided, giving the factorization  {{math|(''a'' − ''b'')(''a'' + ''c'')}}.<ref>{{cite book | last=Harriot | first=T. | title=Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas | publisher=Apud Robertum Barker, typographum regium | year=1631 | url=https://books.google.com/books?id=771CAAAAcAAJ | language=la | mode=cs2}}</ref>

===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 [[polynomial]]s, though they also may be applied when the terms of the sum are not [[monomial]]s, 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 property|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,<ref>{{harvnb|Fite|1921|p=19}}</ref>
<math display="block">6 x^3 y^2 + 8 x^4 y^3 - 10 x^5 y^3 = 2 x^3 y^2(3 + 4xy - 5 x^2 y),</math>
since 2 is the greatest common divisor of 6, 8, and 10, and <math>x^3y^2</math> divides all terms.

====Grouping====
Grouping terms may allow using other methods for getting a factorization.

For example, to factor 
<math display="block">4x^2 + 20x + 3xy + 15y, </math>
one may remark that the first two terms have a common factor {{mvar|x}}, and the last two terms have the common factor {{mvar|y}}. Thus
<math display="block">4x^2+20x+3xy+15y = (4x^2+20x) + (3xy+15y) = 4x(x+5) + 3y(x+5). </math>
Then a simple inspection shows the common factor {{math|''x'' + 5}}, leading to the factorization 
<math display="block">4x^2+20x+3xy+15y = (4x+3y) (x+5).</math>

In general, this works for sums of 4 terms that have been obtained as the product of two [[binomial (polynomial)|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 patterns|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 <math>x^4 + 1.</math> If one introduces the non-real [[square root of –1]], commonly denoted {{mvar|i}}, then one has a [[difference of squares]]
<math display="block">x^4+1=(x^2+i)(x^2-i).</math>
However, one may also want a factorization with [[real number]] coefficients. By adding and subtracting <math>2x^2,</math> and grouping three terms together, one may recognize the square of a [[binomial (polynomial)|binomial]]:
<math display="block">x^4+1 = (x^4+2x^2+1) - 2x^2 = (x^2+1)^2 - \left(x\sqrt2\right)^2 = \left(x^2+x\sqrt2+1\right) \left(x^2-x\sqrt2+1\right).</math>
Subtracting and adding <math>2x^2</math> also yields the factorization:
<math display="block">x^4+1 = (x^4-2x^2+1)+2x^2 = (x^2-1)^2 + \left(x\sqrt2\right)^2 = \left(x^2+x\sqrt{-2}-1\right) \left(x^2-x\sqrt{-2}-1\right).</math>
These factorizations work not only over the complex numbers, but also over any [[field (mathematics)|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]] <math>x^4 + 1,</math> which is [[irreducible polynomial|irreducible]] over the integers, is reducible [[modular arithmetic|modulo]] every [[prime number]]. For example,
<math display="block">x^4 + 1 \equiv (x+1)^4 \pmod 2;</math>
<math display="block">x^4 + 1 \equiv (x^2+x-1)(x^2-x-1) \pmod 3,</math>since <math>1^2 \equiv -2 \pmod 3;</math>
<math display="block">x^4 + 1 \equiv (x^2+2)(x^2-2) \pmod 5,</math>since <math>2^2 \equiv -1 \pmod 5;</math>
<math display="block">x^4 + 1 \equiv (x^2+3x+1)(x^2-3x+1) \pmod 7,</math>since <math>3^2 \equiv 2 \pmod 7.</math>

===Recognizable patterns===
Many [[identity (mathematics)|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 {{mvar|E}} and {{mvar|F}} that appear in these identities may represent any subexpression of the expression that has to be factorized).<ref>{{harvnb|Selby|1970|p=101}}</ref> 
[[File:Difference_of_squares_and_cubes_visual_proof.svg|thumb|Visual proof of the differences between two squares and two cubes]]
*;[[Difference of two squares]]
::<math> E^2 - F^2 = (E+F)(E-F)</math>
:For example,
:::<math>\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} </math>
*;Sum/difference of two cubes
{{anchor|Sum/difference of two cubes}}
<!-- [[File:Differenceofcubes.jpg|thumb|A visual representation of the factorization of cubes using volumes. For a sum of cubes, simply substitute z=-y.]] -->
::<math> E^3 + F^3 = (E + F)(E^2 - EF + F^2)</math>
::<math> E^3 - F^3 = (E - F)(E^2 + EF + F^2)</math>
:*;[[Cauchy]] identity
:::<math> a^3 + b^3 + 3ab(a+b) = (a+b)^3 </math>
:::<math> a^3 - b^3 - 3ab(a-b) = (a-b)^3 </math>
*;Difference of two fourth powers
::<math>\begin{align}
E^4 - F^4 &= (E^2 + F^2)(E^2 - F^2) \\
&= (E^2 + F^2)(E + F)(E - F)
\end{align}</math>
*;Sum/difference of two {{mvar|n}}th powers
:In the following identities, the factors may often be further factorized:
:*;Difference, even exponent
::<math>E^{2n}-F^{2n}= (E^n+F^n)(E^n-F^n)</math>
:*;Difference, even or odd exponent
::<math> 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} )</math>
::This is an example showing that the factors may be much larger than the sum that is factorized.
:*;Sum, odd exponent
::<math> 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} )</math>
::(obtained by changing {{mvar|F}} by {{math|–''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 {{mvar|E}} and {{mvar|F}} contain complex numbers, this may be not the case). If ''n'' has an odd divisor, that is if {{math|1=''n'' = ''pq''}} with {{mvar|p}} odd, one may use the preceding formula (in "Sum, odd exponent") applied to <math>(E^q)^p+(F^q)^p.</math>

*;Trinomials and cubic formulas
:::<math>
\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}
</math>
:*;[[Jean-Robert Argand | Argand]] identity
:::<math> x^4 + x^2y^2 + y^4 = (x^2 + xy +y^2)(x^2 - xy + y^2)</math>
:::<math> x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)</math>

*;Binomial expansions
[[File:binomial_expansion_visualisation.svg|thumb|300px|Visualisation of binomial expansion up to the 4th power]]
:The [[binomial theorem]] supplies patterns that can easily be recognized from the integers that appear in them 
:In low degree:
::<math> a^2 + 2ab + b^2 = (a + b)^2</math>
::<math> a^2 - 2ab + b^2 = (a - b)^2</math>
::<math> a^3 + 3a^2b + 3ab^2 + b^3 = (a+b)^3 </math>
::<math> a^3 - 3a^2b + 3ab^2 - b^3 = (a-b)^3 </math>
:More generally, the coefficients of the expanded forms of <math>(a+b)^n</math> and <math>(a-b)^n</math> are the [[binomial coefficient]]s, that appear in the {{math|''n''}}th row of [[Pascal's triangle]].

====Roots of unity====
The {{mvar|n}}th [[roots of unity]] are the [[complex number]]s each of which is a [[zero of a function|root]] of the polynomial <math>x^n-1.</math> They are thus the numbers 
<math display="block">e^{2ik\pi/n} = \cos \tfrac{2\pi k}n + i\sin \tfrac{2\pi k} n </math>
for <math>k=0, \ldots, n-1.</math>

It follows that for any two expressions {{mvar|E}} and {{mvar|F}}, one has:
<math display="block">E^n-F^n = (E-F) \prod_{k=1}^{n-1} \left(E-F e^{2ik\pi/n}\right)</math>
<math display="block">E^n + F^n = \prod_{k=0}^{n-1} \left(E-F e^{(2k+1)i\pi/n}\right) \qquad \text{if } n \text{ is even}</math>
<math display="block">E^{n}+F^{n}=(E+F) \prod_{k=1}^{n-1}\left(E+F e^{2ik\pi/n}\right) \qquad \text{if } n \text{ is odd}</math>

If {{mvar|E}} and {{mvar|F}} are real expressions, and one wants real factors, one has to replace every pair of [[complex conjugate]] factors by its product. As the complex conjugate of <math>e^{i\alpha}</math> is <math>e^{-i\alpha},</math> and 
<math display="block">\left(a-be^{i\alpha}\right) \left(a-be^{-i\alpha}\right)=
a^2 - ab\left(e^{i\alpha}+e^{-i\alpha}\right) + b^2e^{i\alpha}e^{-i\alpha} =
a^2 - 2ab\cos\,\alpha + b^2,  </math>
one has the following real factorizations (one passes from one to the other by changing {{mvar|k}} into {{math|''n'' − ''k''}} or {{math|''n'' + 1 − ''k''}}, and applying the usual [[trigonometric formulas]]:
<math display="block">\begin{align}
E^{2n}-F^{2n}&= 
(E-F)(E+F)\prod_{k=1}^{n-1} \left(E^2-2EF \cos\,\tfrac{k\pi}n +F^2\right)\\
&=(E-F)(E+F)\prod_{k=1}^{n-1} \left(E^2+2EF \cos\,\tfrac{k\pi}n +F^2\right)
\end{align}</math>
<math display="block"> \begin{align}
E^{2n} + F^{2n} &= 
\prod_{k=1}^n \left(E^2 + 2EF\cos\,\tfrac{(2k-1)\pi}{2n}+F^2\right)\\
&=\prod_{k=1}^n \left(E^2 - 2EF\cos\,\tfrac{(2k-1)\pi}{2n}+F^2\right)
\end{align}</math>

The [[cosine]]s that appear in these factorizations are [[algebraic number]]s, and may be expressed in terms of [[nth root|radicals]] (this is possible because their [[Galois group]] is cyclic); however, these radical expressions are too complicated to be used, except for low values of {{mvar|n}}. For example,
<math display="block"> a^4 + b^4 = (a^2 - \sqrt 2 ab + b^2)(a^2 + \sqrt 2 ab + b^2).</math>
<math display="block"> a^5 - b^5 = (a - b) \left(a^2 + \frac{1-\sqrt 5}2 ab + b^2\right) \left(a^2 +\frac{1+\sqrt 5}2 ab + b^2\right),</math>
<math display="block"> a^5 + b^5 = (a + b) \left(a^2 - \frac{1-\sqrt 5}2 ab + b^2\right) \left(a^2 -\frac{1+\sqrt 5}2 ab + b^2\right),</math>

Often one wants a factorization with rational coefficients. Such a factorization involves [[cyclotomic polynomial]]s. To express rational factorizations of sums and differences or powers, we need a notation for the [[homogenization of a polynomial]]: if <math>P(x)=a_0x^n+a_ix^{n-1} +\cdots +a_n,</math> its ''homogenization'' is the [[bivariate polynomial]] <math>\overline P(x,y)=a_0x^n+a_ix^{n-1}y +\cdots +a_ny^n.</math> Then, one has
<math display="block">E^n-F^n=\prod_{k\mid n}\overline Q_n(E,F),</math>
<math display="block">E^n+F^n=\prod_{k\mid 2n,k\not\mid n}\overline Q_n(E,F),</math>
where the products are taken over all divisors of {{mvar|n}}, or all divisors of {{math|2''n''}} that do not divide {{mvar|n}}, and <math>Q_n(x)</math> is the {{mvar|n}}th cyclotomic polynomial.

For example, 
<math display="block">a^6-b^6= \overline Q_1(a,b)\overline Q_2(a,b)\overline Q_3(a,b)\overline Q_6(a,b)=(a-b)(a+b)(a^2-ab+b^2)(a^2+ab+b^2),</math>
<math display="block">a^6+b^6=\overline Q_4(a,b)\overline Q_{12}(a,b) = (a^2+b^2)(a^4-a^2b^2+b^4),</math>
since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.

==Polynomials==
{{Main|Factorization of polynomials}}
For polynomials, factorization is strongly related with the problem of solving [[algebraic equation]]s. An algebraic equation has the form
:<math>P(x)\ \,\stackrel{\text{def}}{=}\ \,a_0x^n+a_1x^{n-1}+\cdots+a_n=0,</math>
where {{math|''P''(''x'')}} is a polynomial in {{mvar|x}} with <math>a_0\ne 0.</math>
A solution of this equation (also called a [[zero of a function|root]] of the polynomial) is a value {{mvar|r}} of {{mvar|x}} such that
:<math>P(r)=0.</math>

If <math>P(x)=Q(x)R(x)</math> is a factorization of {{math|1=''P''(''x'') = 0}} as a product of two polynomials, then the roots of {{math|''P''(''x'')}} are the [[Union (set theory)|union]] of the roots of {{math|''Q''(''x'')}} and the roots of {{math|''R''(''x'')}}. Thus solving {{math|1=''P''(''x'') = 0}} is reduced to the simpler problems of solving {{math|1=''Q''(''x'') = 0}} and {{math|1=''R''(''x'') = 0}}.

Conversely, the [[factor theorem]] asserts that, if {{mvar|r}} is a root of {{math|1=''P''(''x'') = 0}}, then {{math|''P''(''x'')}} may be factored as
:<math>P(x)=(x-r)Q(x),</math>
where {{math|''Q''(''x'')}} is the quotient of [[Euclidean division of polynomials|Euclidean division]] of {{math|1=''P''(''x'') = 0}} by the linear (degree one) factor {{math|''x'' − ''r''}}.

If the coefficients of {{math|''P''(''x'')}} are [[real number|real]] or [[complex number|complex]] numbers, the [[fundamental theorem of algebra]] asserts that {{math|''P''(''x'')}} has a real or complex root. Using the factor theorem recursively, it results that
:<math>P(x)=a_0(x-r_1)\cdots (x-r_n),</math>
where <math>r_1, \ldots, r_n</math> are the real or complex roots of {{mvar|P}}, with some of them possibly repeated. This complete factorization is unique [[up to]] the order of the factors.

If the coefficients of {{math|''P''(''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, if {{math|1=''r'' = ''a'' + ''ib''}} is a non-real root of {{math|''P''(''x'')}}, then its [[complex conjugate]] {{math|1=''s'' = ''a'' − ''ib''}} is also a root of {{math|''P''(''x'')}}. So, the product 
:<math>(x-r)(x-s) = x^2-(r+s)x+rs = x^2-2ax+a^2+b^2</math>
is a factor of {{math|''P''(''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 using [[root-finding algorithm]]s.

In practice, most algebraic equations of interest have [[integer]] or [[rational number|rational]] coefficients, and one may want a factorization with factors of the same kind. The [[fundamental theorem of arithmetic]] may be generalized to this case, stating that polynomials with integer or rational coefficients have the [[unique factorization domain|unique factorization property]]. More precisely, every polynomial with rational coefficients may be factorized in a product
:<math>P(x)=q\,P_1(x)\cdots P_k(x),</math>
where {{mvar|q}} is a rational number and <math>P_1(x), \ldots, P_k(x)</math> are non-constant polynomials with integer coefficients that are [[irreducible polynomial|irreducible]] and [[primitive polynomial (ring theory)|primitive]]; this means that none of the <math>P_i(x)</math> 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 efficient [[algorithm]]s for computing this factorization, which are implemented in most [[computer algebra]] systems. See [[Factorization 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.

===Primitive-part & content factorization===
{{Main|Polynomial factorization#Primitive part–content factorization}}

Every polynomial with [[rational number|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 polynomial (ring theory)|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:
:<math>-10x^2 + 5x + 5 = (-5)\cdot (2x^2 - x - 1)</math>
:<math>\frac{1}{3}x^5 + \frac{7}{2} x^2 + 2x + 1 = \frac{1}{6} ( 2x^5 + 21x^2 + 12x + 6)</math>

In this factorization, the rational number is called the [[primitive part and content|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 {{mvar|q}} of a polynomial with integer coefficients. Then one divides out the greater common divisor {{mvar|p}} of the coefficients of this polynomial for getting the primitive part, the content being <math>p/q.</math> Finally, if needed, one changes the signs of {{mvar|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 integers|coprime]] denominators), but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.

===Using the factor theorem===
{{Main|Factor theorem}}

The factor theorem states that, if {{mvar|r}} is a [[zero of a function|root]] of a [[polynomial]]
:<math>P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,</math>
meaning {{math|1=''P''(''r'') = 0}}, then there is a factorization 
:<math>P(x)=(x-r)Q(x),</math>
where 
:<math>Q(x)=b_0x^{n-1}+\cdots+b_{n-2}x+b_{n-1},</math>
with <math>a_0=b_0</math>. Then [[polynomial long division]] or [[synthetic division]] give:
:<math>b_i=a_0r^i +\cdots+a_{i-1}r+a_i \ \text{ for }\ i = 1,\ldots,n{-}1.</math>
This may be useful when one knows or can guess a root of the polynomial.

For example, for <math>P(x) = x^3 - 3x + 2,</math> one may easily see that the sum of its coefficients is 0, so {{math|1=''r'' = 1}} is a root. As {{math|1=''r'' + 0 = 1}}, and <math>r^2 +0r-3=-2,</math> one has 
:<math>x^3 - 3x + 2 = (x - 1)(x^2 + x - 2).</math>

===Rational roots===
For polynomials with rational number coefficients, one may search for roots which are rational numbers. Primitive part-content factorization (see [[#Primitive part-content factorization|above]]) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivial [[greatest common divisor|common divisor]].

If <math>x=\tfrac pq</math> is a rational root of such a polynomial 
:<math>P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,</math>
the factor theorem shows that one has a factorization
:<math>P(x)=(qx-p)Q(x),</math>
where both factors have integer coefficients (the fact that {{mvar|Q}} has integer coefficients results from the above formula for the quotient of {{math|''P''(''x'')}} by <math>x-p/q</math>).

Comparing the coefficients of degree {{mvar|n}} and the constant coefficients in the above equality shows that, if <math>\tfrac pq</math> is a rational root in [[reduced fraction|reduced form]], then {{mvar|q}} is a divisor of <math>a_0,</math> and {{mvar|p}} is a divisor of <math>a_n.</math> Therefore, there is a finite number of possibilities for {{mvar|p}} and {{mvar|q}}, which can be systematically examined.<ref>{{harvnb|Dickson|1922|p=27}}</ref>

For example, if the polynomial 
:<math>P(x)=2x^3 - 7x^2 + 10x - 6</math>
has a rational root <math>\tfrac pq</math> with {{math|''q'' > 0}}, then {{mvar|p}} must divide 6; that is <math>p\in\{\pm 1,\pm 2,\pm3, \pm 6\}, </math> and {{mvar|q}} must divide 2, that is <math>q\in\{1, 2\}. </math> Moreover, if {{math|''x'' < 0}}, all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have 
:<math>\tfrac pq \in \{1, 2, 3, 6, \tfrac 12, \tfrac 32\}.</math>
A direct computation shows that only <math>\tfrac 32</math> is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization
<math>2x^3 - 7x^2 + 10x - 6 = (2x -3)(x^2 -2x + 2).</math>

====Quadratic ac method====
The above method may be adapted for [[quadratic polynomial]]s, leading to the ''ac method'' of factorization.<ref>{{cite web|last=Stover|first=Christopher|url=http://mathworld.wolfram.com/ACMethod.html|title=AC Method|work=Mathworld|archive-url=https://web.archive.org/web/20141112231252/http://mathworld.wolfram.com/ACMethod.html|archive-date=2014-11-12|url-status=live|mode=cs2}}</ref>

Consider the quadratic polynomial 
:<math>P(x)=ax^2 + bx + c</math>
with integer coefficients. If it has a rational root, its denominator must divide {{math|''a''}} evenly and it may be written as a possibly [[irreducible fraction|reducible fraction]] <math>r_1 = \tfrac ra.</math> By [[Vieta's formulas]], the other root <math>r_2</math> is
:<math>r_2 = -\frac ba - r_1 = -\frac ba-\frac ra =-\frac{b+r}a = \frac sa,</math>
with <math>s=-(b+r).</math>
Thus the second root is also rational, and Vieta's second formula <math>r_1 r_2=\frac ca</math> gives
:<math>\frac sa\frac ra =\frac ca,</math>
that is 
:<math>rs=ac\quad \text{and}\quad r+s=-b.</math>
Checking all pairs of integers whose product is {{math|''ac''}} gives the rational roots, if any.

In summary, if <math>ax^2 +bx+c</math> has rational roots there are integers {{mvar|r}} and {{mvar|s}} such <math>rs=ac</math> and <math>r+s=-b</math> (a finite number of cases to test), and the roots are <math>\tfrac ra</math> and <math>\tfrac sa.</math> In other words, one has the factorization
:<math>a(ax^2+bx+c) = (ax-r)(ax-s).</math>

For example, let consider the quadratic polynomial
:<math>6x^2 + 13x + 6.</math>
Inspection of the factors of {{math|1=''ac'' = 36}} leads to {{math|1=4 + 9 = 13 = ''b''}}, giving the two roots 
:<math>r_1 = -\frac 46 =-\frac 23 \quad \text{and} \quad r_2 = -\frac96 = -\frac 32,</math>

and the factorization 
:<math>
6x^2 + 13x + 6 = 6(x+\tfrac 23)(x+\tfrac 32)= (3x+2)(2x+3).
</math>

===Using formulas for polynomial roots===
Any univariate [[quadratic polynomial]] <math>ax^2+bx+c</math> can be factored using the [[quadratic formula]]:
:<math>
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),
</math>
where <math>\alpha</math> and <math>\beta</math> are the two [[zero of a function|roots]] of the polynomial.

If {{math|''a, b, c''}} are all [[real number|real]], the factors are real if and only if the [[discriminant]] <math>b^2-4ac</math> 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 (mathematics)|field]] of [[Characteristic (algebra)|characteristic]] different from two, and, in particular, for coefficients in a [[finite field]] with an odd number of elements.<ref>In a field of characteristic 2, one has 2 = 0, and the formula produces a division by zero.</ref>

There are also formulas for roots of [[cubic function|cubic]] and [[quartic function|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.

===Using relations between roots===
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 <math>x_1</math>
and <math>x_2</math> of a polynomial <math>P(x)</math> satisfy the relation
:<math>x_2=Q(x_1),</math>
where {{mvar|Q}} is a polynomial.

This implies that <math>x_1</math> is a common root of <math>P(Q(x))</math> and <math>P(x).</math> It is therefore a root of the [[Polynomial greatest common divisor|greatest common divisor]] of these two polynomials. It follows that this greatest common divisor is a non constant factor of <math>P(x).</math> [[Euclidean algorithm for polynomials]] allows computing this greatest common factor.

For example,<ref>{{harvnb|Burnside|Panton|1960|p=38}}</ref> if one know or guess that:
<math>P(x)=x^3 -5x^2 -16x +80</math> 
has two roots that sum to zero, one may apply Euclidean algorithm to <math>P(x)</math> and <math>P(-x).</math> The first division step consists in adding <math>P(x)</math> to <math>P(-x),</math> giving the [[remainder]] of 
:<math>-10(x^2-16).</math>
Then, dividing <math>P(x)</math> by <math>x^2-16</math> gives zero as a new remainder, and {{math|''x'' − 5}} as a quotient, leading to the complete factorization
:<math>x^3 - 5x^2 - 16x + 80 = (x -5)(x-4)(x+4).</math>

==Unique factorization domains==

The integers and the polynomials over a [[field (mathematics)|field]] share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a [[unit (ring theory)|unit]], ±1 in the case of integers) and a product of [[irreducible element]]s ([[prime number]]s, in the case of integers), and this factorization is unique up to rearranging the factors and shifting units among the factors. [[Integral domain]]s which share this property are called [[unique factorization domain]]s (UFD).

[[Greatest common divisor]]s 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 (mathematics)|field]] {{mvar|F}} such that there cannot exist any factorization algorithm in the Euclidean domain {{math|''F''[''x'']}} of the univariate polynomials over {{mvar|F}}.

==Ideals==
{{Main|Dedekind domain}}
In [[algebraic number theory]], the study of [[Diophantine equation]]s led mathematicians, during 19th century, to introduce generalizations of the [[integer]]s called [[algebraic integer]]s. The first [[ring of algebraic integers]] that have been considered were [[Gaussian integer]]s and [[Eisenstein integer]]s, which share with usual integers the property of being [[principal ideal domain]]s, and have thus the [[unique factorization domain|unique factorization property]].

Unfortunately, it soon appeared that most rings of algebraic integers are not principal and do not have unique factorization. The simplest example is <math>\mathbb Z[\sqrt{-5}],</math> in which
:<math>9=3\cdot 3 = (2+\sqrt{-5})(2-\sqrt{-5}),</math>
and all these factors are [[irreducible element|irreducible]].

This lack of unique factorization is a major difficulty for solving Diophantine equations. For example, many wrong proofs of [[Fermat's Last Theorem]] (probably including [[Pierre de Fermat|Fermat'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 by [[Richard Dedekind|Dedekind]], who proved that the rings of algebraic integers have unique factorization of [[ideal (ring theory)|ideals]]: in these rings, every ideal is a product of [[prime ideal]]s, and this factorization is unique up the order of the factors. The [[integral domain]]s that have this unique factorization property are now called [[Dedekind domain]]s. They have many nice properties that make them fundamental in algebraic number theory.

==Matrices==

Matrix rings are non-commutative and have no unique factorization: there are, in general, many ways of writing a [[matrix (mathematics)|matrix]] as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the [[LU decomposition]] gives a matrix as the product of a [[lower triangular matrix]] by an [[upper triangular matrix]]. As this is not always possible, one generally considers the "LUP decomposition" having a [[permutation matrix]] as its third factor.

See [[Matrix decomposition]] for the most common types of matrix factorizations.

A [[logical matrix]] represents a [[binary relation]], and [[matrix multiplication]] corresponds to [[composition of relations]]. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a [[difunctional]] relation.

==See also==
<!-- PLEASE RESPECT ALPHABETICAL ORDER -->
*[[Euler's factorization method]] for integers
*[[Fermat's factorization method]] for integers
*[[Monoid factorisation]]
*[[Multiplicative partition]]
*[[Table of Gaussian integer factorizations]]

==Notes==
{{Reflist}}

==References==
* {{citation|first1=William Snow|last1=Burnside|author-link1=William Burnside|first2=Arthur William|last2=Panton|title=The Theory of Equations with an introduction to the theory of binary algebraic forms (Volume one)|year=1960|orig-year=1912|publisher=Dover}}
* {{citation|first=Leonard Eugene|last=Dickson|author-link=Leonard Eugene Dickson|title=First Course in the Theory of Equations|journal=Nature |year=1922|volume=109 |issue=2746 |page=773 |publisher=John Wiley & Sons|doi=10.1038/109773c0 |bibcode=1922Natur.109R.773. |place=New York}}
* {{citation|first=William Benjamin|last=Fite|title=College Algebra (Revised)|year=1921|publisher=D. C. Heath & Co.|place=Boston}}
* {{citation|first=Felix|last=Klein|author-link=Felix Klein|title=Elementary Mathematics from an Advanced Standpoint; Arithmetic, Algebra, Analysis|year=1925|publisher=Dover}}
* {{citation|first=Samuel M. |last=Selby|year=1970|title=CRC Standard Mathematical Tables|edition=18th|publisher=The Chemical Rubber Co.}}

==External links==
{{Wiktionary|factorisation|factorization}}
* [[Wolfram Alpha]] [http://www.wolframalpha.com/input/?i=Factor%20-2006+%2B+1155+x+-+78+x^2+%2B+x^3 can factorize too].

{{Authority control}}

[[Category:Arithmetic]]
[[Category:Elementary algebra]]
[[Category:Factorization]]