Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Factorization
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==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>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)