Factorization

For factoring n = 1386 into primes:

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

1386 = 2 · 3² · 7 · 11.

The systematic use of algebraic manipulations for simplifying expressions (more specifically equations)) 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.[3] 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 aa − 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 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.

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,[5]

${\displaystyle 6x^{3}y^{2}+8x^{4}y^{3}-10x^{5}y^{3}=2x^{3}y^{2}(3+4xy-5x^{2}y),}$

since 2 is the greatest common divisor of 6, 8, and 10, and ${\displaystyle x^{3}y^{2}}$ divides all terms.

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

For example, to factor

${\displaystyle 4x^{2}+20x+3xy+15y,}$

one may remark that the first two terms have a common factor x, and the last two terms have the common factor y. Thus

${\displaystyle 4x^{2}+20x+3xy+15y=(4x^{2}+20x)+(3xy+15y)=4x(x+5)+3y(x+5).}$

Then a simple inspection shows the common factor x + 5, leading to the factorization

${\displaystyle 4x^{2}+20x+3xy+15y=(4x+3y)(x+5).}$

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.

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 ${\displaystyle x^{4}+1.}$ If one introduces the non-real square root of –1, commonly denoted i, then one has a difference of squares

${\displaystyle x^{4}+1=(x^{2}+i)(x^{2}-i).}$

However, one may also want a factorization with real number coefficients. By adding and subtracting ${\displaystyle 2x^{2},}$ and grouping three terms together, one may recognize the square of a binomial:

${\displaystyle x^{4}+1=(x^{4}+2x^{2}+1)-2x^{2}=(x^{2}+1)^{2}-\left(x{\sqrt {2}}\right)^{2}=\left(x^{2}+x{\sqrt {2}}+1\right)\left(x^{2}-x{\sqrt {2}}+1\right).}$

Subtracting and adding ${\displaystyle 2x^{2}}$ also yields the factorization:

${\displaystyle x^{4}+1=(x^{4}-2x^{2}+1)+2x^{2}=(x^{2}-1)^{2}+\left(x{\sqrt {2}}\right)^{2}=\left(x^{2}+x{\sqrt {-2}}-1\right)\left(x^{2}-x{\sqrt {-2}}-1\right).}$

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 ${\displaystyle x^{4}+1,}$ which is irreducible over the integers, is reducible modulo every prime number. For example,

${\displaystyle x^{4}+1\equiv (x+1)^{4}{\pmod {2}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+x-1)(x^{2}-x-1){\pmod {3}},\qquad }$since ${\displaystyle 1^{2}\equiv -2{\pmod {3}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+2)(x^{2}-2){\pmod {5}},\qquad }$since ${\displaystyle 2^{2}\equiv -1{\pmod {5}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+3x+1)(x^{2}-3x+1){\pmod {7}},\qquad }$since ${\displaystyle 3^{2}\equiv 2{\pmod {7}}.}$

Many 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 E and F 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

• Difference of two squares

${\displaystyle E^{2}-F^{2}=(E+F)(E-F)}$

For example,

${\displaystyle {\begin{aligned}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{aligned}}}$

• Sum/difference of two cubes

${\displaystyle E^{3}+F^{3}=(E+F)(E^{2}-EF+F^{2})}$

${\displaystyle E^{3}-F^{3}=(E-F)(E^{2}+EF+F^{2})}$

• Difference of two fourth powers

${\displaystyle {\begin{aligned}E^{4}-F^{4}&=(E^{2}+F^{2})(E^{2}-F^{2})\\&=(E^{2}+F^{2})(E+F)(E-F)\end{aligned}}}$

• Sum/difference of two nth powers

In the following identities, the factors may often be further factorized:

• Difference, even exponent

${\displaystyle E^{2n}-F^{2n}=(E^{n}+F^{n})(E^{n}-F^{n})}$

• Difference, even or odd exponent

${\displaystyle 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})}$

This is an example showing that the factors may be much larger than the sum that is factorized.

• Sum, odd exponent

${\displaystyle 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})}$

(obtained by changing F by –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 E and F contain complex numbers, this may be not the case). If n has an odd divisor, that is if n = pq with p odd, one may use the preceding formula (in "Sum, odd exponent") applied to ${\displaystyle (E^{q})^{p}+(F^{q})^{p}.}$

• Trinomials and cubic formulas

${\displaystyle {\begin{aligned}&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^{4}+x^{2}y^{2}+y^{4}=(x^{2}+xy+y^{2})(x^{2}-xy+y^{2}).\end{aligned}}}$

• Binomial expansions

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:

${\displaystyle a^{2}+2ab+b^{2}=(a+b)^{2}}$

${\displaystyle a^{2}-2ab+b^{2}=(a-b)^{2}}$

${\displaystyle a^{3}+3a^{2}b+3ab^{2}+b^{3}=(a+b)^{3}}$

${\displaystyle a^{3}-3a^{2}b+3ab^{2}-b^{3}=(a-b)^{3}}$

More generally, the coefficients of the expanded forms of ${\displaystyle (a+b)^{n}}$ and ${\displaystyle (a-b)^{n}}$ are the binomial coefficients, that appear in the nth row of Pascal's triangle.

The nth roots of unity are the complex numbers each of which is a root of the polynomial ${\displaystyle x^{n}-1.}$ They are thus the numbers

${\displaystyle e^{2ik\pi /n}=\cos {\tfrac {2\pi k}{n}}+i\sin {\tfrac {2\pi k}{n}}}$

for ${\displaystyle k=0,\ldots ,n-1.}$

It follows that for any two expressions E and F, one has:

${\displaystyle E^{n}-F^{n}=(E-F)\prod _{k=1}^{n-1}\left(E-Fe^{2ik\pi /n}\right)}$

${\displaystyle E^{n}+F^{n}=\prod _{k=0}^{n-1}\left(E-Fe^{(2k+1)i\pi /n}\right)\qquad {\text{if }}n{\text{ is even}}}$

${\displaystyle E^{n}+F^{n}=(E+F)\prod _{k=1}^{n-1}\left(E+Fe^{2ik\pi /n}\right)\qquad {\text{if }}n{\text{ is odd}}}$

If E and 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 ${\displaystyle e^{i\alpha }}$ is ${\displaystyle e^{-i\alpha },}$ and

${\displaystyle \left(a-be^{i\alpha }\right)\left(a-be^{-i\alpha }\right)=a^{2}-ab\left(e^{i\alpha }+e^{-i\alpha }\right)+b^{2}e^{i\alpha }e^{-i\alpha }=a^{2}-2ab\cos \,\alpha +b^{2},}$

one has the following real factorizations (one passes from one to the other by changing k into n – k or n + 1 – k, and applying the usual trigonometric formulas:

${\displaystyle {\begin{aligned}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{aligned}}}$

${\displaystyle {\begin{aligned}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{aligned}}}$

The cosines that appear in these factorizations are algebraic numbers, and may be expressed in terms of 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 n. For example,

${\displaystyle a^{4}+b^{4}=(a^{2}-{\sqrt {2}}ab+b^{2})(a^{2}+{\sqrt {2}}ab+b^{2}).}$

${\displaystyle 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),}$

${\displaystyle 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),}$

Often one wants a factorization with rational coefficients. Such a factorization involves cyclotomic polynomials. To express rational factorizations of sums and differences or powers, we need a notation for the homogenization of a polynomial: if ${\displaystyle P(x)=a_{0}x^{n}+a_{i}x^{n-1}+\cdots +a_{n},}$ its homogenization is the bivariate polynomial ${\displaystyle {\overline {P}}(x,y)=a_{0}x^{n}+a_{i}x^{n-1}y+\cdots +a_{n}y^{n}.}$ Then, one has

${\displaystyle E^{n}-F^{n}=\prod _{k\mid n}{\overline {Q}}_{n}(E,F),}$

${\displaystyle E^{n}+F^{n}=\prod _{k\mid 2n,k\not \mid n}{\overline {Q}}_{n}(E,F),}$

where the products are taken over all divisors of n, or all divisors of 2n that do not divide n, and ${\displaystyle Q_{n}(x)}$ is the nth cyclotomic polynomial.

For example,

${\displaystyle 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}),}$

${\displaystyle a^{6}+b^{6}={\overline {Q}}_{4}(a,b){\overline {Q}}_{12}(a,b)=(a^{2}+b^{2})(a^{4}-a^{2}b^{2}+b^{4}),}$

since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.

Every polynomial with 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 (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:

${\displaystyle -10x^{2}+5x+5=(-5)\cdot (2x^{2}-x-1)}$

${\displaystyle {\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6)}$

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

The factor theorem states that, if r is a root of a polynomial

${\displaystyle P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},}$

meaning P(r) = 0, then there is a factorization

${\displaystyle P(x)=(x-r)Q(x),}$

where

${\displaystyle Q(x)=b_{0}x^{n-1}+\cdots +b_{n-2}x+b_{n-1},}$

with ${\displaystyle a_{0}=b_{0}}$. Then polynomial long division or synthetic division give:

${\displaystyle b_{i}=a_{0}r^{i}+\cdots +a_{i-1}r+a_{i}\ {\text{ for }}\ i=1,\ldots ,n{-}1.}$

This may be useful when one knows or can guess a root of the polynomial.

For example, for ${\displaystyle P(x)=x^{3}-3x+2,}$ one may easily see that the sum of its coefficients is 0, so r = 1 is a root. As r + 0 = 1, and ${\displaystyle r^{2}+0r-3=-2,}$ one has

${\displaystyle x^{3}-3x+2=(x-1)(x^{2}+x-2).}$

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

If ${\displaystyle x={\tfrac {p}{q}}}$ is a rational root of such a polynomial

${\displaystyle P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},}$

the factor theorem shows that one has a factorization

${\displaystyle P(x)=(qx-p)Q(x),}$

where both factors have integer coefficients (the fact that Q has integer coefficients results from the above formula for the quotient of P(x) by ${\displaystyle x-p/q}$).

Comparing the coefficients of degree n and the constant coefficients in the above equality shows that, if ${\displaystyle {\tfrac {p}{q}}}$ is a rational root in reduced form, then q is a divisor of ${\displaystyle a_{0},}$ and p is a divisor of ${\displaystyle a_{n}.}$ Therefore, there is a finite number of possibilities for p and q, which can be systematically examined.[7]

For example, if the polynomial

${\displaystyle P(x)=2x^{3}-7x^{2}+10x-6}$

has a rational root ${\displaystyle {\tfrac {p}{q}}}$ with q > 0, then p must divide 6; that is ${\displaystyle p\in \{\pm 1,\pm 2,\pm 3,\pm 6\},}$ and q must divide 2, that is ${\displaystyle q\in \{1,2\}.}$ Moreover, if x < 0, all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have

${\displaystyle {\tfrac {p}{q}}\in \{1,2,3,6,{\tfrac {1}{2}},{\tfrac {3}{2}}\}.}$

A direct computation shows that only ${\displaystyle {\tfrac {3}{2}}}$ is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization ${\displaystyle 2x^{3}-7x^{2}+10x-6=(2x-3)(x^{2}-2x+2).}$

The above method may be adapted for quadratic polynomials, leading to the ac method of factorization.[8]

Consider the quadratic polynomial

${\displaystyle P(x)=ax^{2}+bx+c}$

with integer coefficients. If it has a rational root, its denominator must divide a evenly and it may be written as a possibly reducible fraction ${\displaystyle r_{1}={\tfrac {r}{a}}.}$ By Vieta's formulas, the other root ${\displaystyle r_{2}}$ is

${\displaystyle r_{2}=-{\frac {b}{a}}-r_{1}=-{\frac {b}{a}}-{\frac {r}{a}}=-{\frac {b+r}{a}}={\frac {s}{a}},}$

with ${\displaystyle s=-(b+r).}$ Thus the second root is also rational, and Vieta's second formula ${\displaystyle r_{1}r_{2}={\frac {c}{a}}}$ gives

${\displaystyle {\frac {s}{a}}{\frac {r}{a}}={\frac {c}{a}},}$

that is

${\displaystyle rs=ac\quad {\text{and}}\quad r+s=-b.}$

Checking all pairs of integers whose product is ac gives the rational roots, if any.

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

${\displaystyle a(ax^{2}+bx+c)=(ax-r)(ax-s).}$

For example, let consider the quadratic polynomial

${\displaystyle 6x^{2}+13x+6.}$

Inspection of the factors of ac = 36 leads to 4 + 9 = 13 = b, giving the two roots

${\displaystyle r_{1}=-{\frac {4}{6}}=-{\frac {2}{3}}\quad {\text{and}}\quad r_{2}=-{\frac {9}{6}}=-{\frac {3}{2}},}$

and the factorization

${\displaystyle 6x^{2}+13x+6=6(x+{\tfrac {2}{3}})(x+{\tfrac {3}{2}})=(3x+2)(2x+3).}$

Any univariate quadratic polynomial ${\displaystyle ax^{2}+bx+c}$ can be factored using the quadratic formula:

${\displaystyle 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),}$

where ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are the two roots of the polynomial.

If a, b, c are all real, the factors are real if and only if the discriminant ${\displaystyle b^{2}-4ac}$ 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 of characteristic different from two, and, in particular, for coefficients in a finite field with an odd number of elements.[9]

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

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 ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ of a polynomial ${\displaystyle P(x)}$ satisfy the relation

${\displaystyle x_{2}=Q(x_{1}),}$

where Q is a polynomial.

This implies that ${\displaystyle x_{1}}$ is a common root of ${\displaystyle P(Q(x))}$ and ${\displaystyle P(x).}$ It is therefore a root of the greatest common divisor of these two polynomials. It follows that this greatest common divisor is a non constant factor of ${\displaystyle P(x).}$ Euclidean algorithm for polynomials allows computing this greatest common factor.

For example,[10] if one know or guess that: ${\displaystyle P(x)=x^{3}-5x^{2}-16x+80}$ has two roots that sum to zero, one may apply Euclidean algorithm to ${\displaystyle P(x)}$ and ${\displaystyle P(-x).}$ The first division step consists in adding ${\displaystyle P(x)}$ to ${\displaystyle P(-x),}$ giving the remainder of

${\displaystyle -10(x^{2}-16).}$

Then, dividing ${\displaystyle P(x)}$ by ${\displaystyle x^{2}-16}$ gives zero as a new remainder, and x – 5 as a quotient, leading to the complete factorization

${\displaystyle x^{3}-5x^{2}-16x+80=(x-5)(x-4)(x+4).}$