Editing Factorization (section)

==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.