Factorization

For factorization algorithms, see Integer factorization and Factorization of polynomials. For other uses, see Factor (disambiguation).

The polynomial x² + cx + d, where a + b = c and ab = d, can be factorized into (x + a)(x + b).

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is a factorization of the integer 15, and (x – 2)(x + 2) is a factorization of the polynomial x² – 4.

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

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. Matrices possess many kinds of matrix factorizations. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix L with all diagonal entries equal to one, an upper triangular matrix U, and a permutation matrix P; this is a matrix formulation of Gaussian elimination.

Integers

Main article: 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 numbers, which are those integers which cannot be further factorized into the product of integers greater than one.

For computing the factorization of an integer n, one needs an algorithm for finding a divisor q of n or deciding that n is prime. When such a divisor is found, the repeated application of this algorithm to the factors q and n / q gives eventually the complete factorization of n.

For finding a divisor q of n, if any, it suffices to test all values of q such that 1 < q and q² ≤ n. In fact, if r is a divisor of n such that r² > n, then q = n / r is a divisor of n such that q² ≤ n.

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

There is no need to test all values of 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 > 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

$1+2^{2^{5}}=1+2^{32}=4\,294\,967\,297$

is not a prime number. In fact, applying the above method would require more than 10000 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 the RSA cryptosystem, which is widely used for secure internet communication.

Example

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.

Expressions

Manipulating 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 E⋅F = 0, then the problem of solving the equation splits into two independent (and generally easier) problems E = 0 and 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,

$x^{3}-ax^{2}-bx^{2}-cx^{2}+abx+acx+bcx-abc$

having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression

$(x-a)(x-b)(x-c),$

with only two multiplications and three subtractions. Moreover, the factored form immediately gives 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, $x^{10}-1$ can be factored into two irreducible factors $x-1$ and $x^{9}+x^{8}+\cdots +x^{2}+x+1$.

Various methods have been developed for finding factorizations; some are described below.

Solving algebraic equations may be viewed as a problem of polynomial factorization. In fact, the fundamental theorem of algebra can be stated as follows: every polynomial in x of degree n with complex coefficients may be factorized into n linear factors $x-a_{i},$ for i = 1, ..., n, where the a_is are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the a_is generally cannot be computed in terms of radicals (n^th roots), by the Abel–Ruffini theorem. In most cases, the best that can be done is computing approximate values of the roots with a root-finding algorithm.

History of factorization of expressions

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

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

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 law allows factoring out this common factor. If there are several such common factors, it is worth 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,

$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 $x^{3}y^{2}$ divides all terms.

Grouping

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

For example, to factor

$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

$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

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

Adding and subtracting terms

Sometimes, some term grouping lets appear a part of a recognizable pattern. It is then useful to add terms for completing the pattern, and subtract them for not changing the value of the expression.

A typical use of this is the completing the square method for getting quadratic formula.

Another example is the factorization of $x^{4}+1.$ If one introduces the non-real square root of –1, commonly denoted i, then one has a difference of squares

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

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

$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 $2x^{2}$ also yields the factorization:

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

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

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

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

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

Recognizable patterns

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.

Visual proof of the differences between two squares and two cubes

• Difference of two squares

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

For example,

${\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

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

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

• Difference of two fourth powers

${\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

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

• Difference, even or odd exponent

$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

$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 $(E^{q})^{p}+(F^{q})^{p}.$

• Trinomials and cubic formulas

${\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:

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

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

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

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

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

Roots of unity

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

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

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

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

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

$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}}$

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

$\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:

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

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

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

$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),$

$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 $P(x)=a_{0}x^{n}+a_{i}x^{n-1}+\cdots +a_{n},$ its homogenization is the bivariate polynomial ${\overline {P}}(x,y)=a_{0}x^{n}+a_{i}x^{n-1}y+\cdots +a_{n}y^{n}.$ Then, one has

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

$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 $Q_{n}(x)$ is the nth cyclotomic polynomial.

For example,

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

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

Polynomials

Main article: Factorization of polynomials

Quadratic polynomials

Any quadratic polynomial over the complex numbers (polynomials of the form $ax^{2}+bx+c$ where $a$, $b$, and $c$ ∈ $\mathbb {C}$) can be factored into an expression with the form $a(x-\alpha )(x-\beta )\$ using the quadratic formula. The method is as follows:

${\begin{aligned}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),\end{aligned}}$

where $\alpha$ and $\beta$ are the two roots of the polynomial, found with the quadratic formula.

Polynomials factorable over the integers

Quadratic polynomials can sometimes be factored into two binomials with simple integer coefficients by use of Vieta's formulas, without the need to use the quadratic formula. In a quadratic equation, this will expose its two roots. The formula

$ax^{2}+bx+c,\,\!$

would be factored into:

$(mx+p)(nx+q),\,\!$

where

$mn=a,\ pq=c\,\!$

and

$pn+mq=b.\,$

Each binomial can then be set equal to zero, and solving for x reveals the two roots.

Consider for example 2x² − 5x + 2 = 0. Because a = 2 and mn = a, mn = 2, which means that of m and n, one is 1 and the other is 2. Now we have (2x + p)(x + q) = 0. Because c = 2 and pq = c, pq = 2, which means that of p and q, one is 1 and the other is 2 or one is −1 and the other is −2. A guess and check of substituting the 1 and 2, and −1 and −2, into p and q (while applying pn + mq = b) tells us that 2x² − 5x + 2 = 0 factors into (2x − 1)(x − 2) = 0, giving us the roots x = {0.5, 2}.

Note: A quick way to check whether the second term in the binomial should be positive or negative (in the example, 1 and 2 and −1 and −2) is to check the second operation in the trinomial (+ or −). If it is +, then check the first operation: if it is +, the terms will be positive, while if it is −, the terms will be negative. If the second operation is −, there will be one positive and one negative term; guess and check is the only way to determine which one is positive and which is negative.

If a polynomial with integer coefficients has a discriminant that is a perfect square, that polynomial is factorable over the integers. For example, consider the polynomial 2x² + 2x − 12. If the values of the expression are substituted into the quadratic formula, the discriminant b² − 4ac becomes 2² − (4 × 2 × (−12)), which equals 100. 100 is a perfect square, so the polynomial 2x² + 2x − 12 is factorable over the integers; its factors are 2, (x − 2), and (x + 3).

Now consider the polynomial x² + 93x − 2. Its discriminant, 93² − 4 × 1 × (−2), is equal to 8657, which is not a perfect square. So x² + 93x − 2 cannot be factored over the integers.

Perfect square trinomials

A visual illustration of the identity (a + b)² = a² + 2ab + b²

Some quadratics can be factored into two identical binomials. These quadratics are called perfect square trinomials. Perfect square trinomials can be factored as follows:

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

and

$a^{2}-2ab+b^{2}=(a-b)^{2}.\,\!$

Sum/difference of two squares

Main article: Difference of two squares

Another common type of algebraic factoring is called the difference of two squares. It is the application of the formula

$a^{2}-b^{2}=(a+b)(a-b),\,\!$

to any two terms, whether or not they are perfect squares. If the two terms are subtracted, simply apply the formula. If they are added, the two binomials obtained from the factoring will each have an imaginary term. This formula can be represented as

$a^{2}+b^{2}=(a+bi)(a-bi).\,\!$

For example, $4x^{2}+49$ can be factored into $(2x+7i)(2x-7i)$.

Factoring by grouping

Another way to factor some polynomials is factoring by grouping. For those who like algorithms, “factoring by grouping” may be the best way to approach factoring a trinomial, as it takes the guess work out of the process.

Factoring by grouping is done by placing the terms in the polynomial into two or more groups, where each group can be factored by a known method. The results of these factorizations can sometimes be combined to make an even more simplified expression. For example, to factor the polynomial

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

Group similar terms, $(4x^{2}+20x)+(3yx+15y)\,$

Factor out greatest common factor, $4x(x+5)+3y(x+5)\,$

Factor out binomial $(x+5)(4x+3y)\,$

AC Method

If a quadratic polynomial has rational solutions, we can find p and q so that pq = ac and p + q = b. (If the discriminant is a square number these exist, otherwise we have irrational or complex solutions, and the assumption of rational solutions is not valid.)

${\begin{aligned}ax^{2}+bx+c&={\frac {a^{2}x^{2}+abx+ac}{a}}&={\frac {(ax+p)(ax+q)}{a}}\end{aligned}}$

The terms on top will have common factors that can be factored out and used to cancel the denominator, if it is not 1. As an example consider the quadratic polynomial:

${\begin{aligned}6x^{2}+13x+6\end{aligned}}$

Inspection of the factors of ac = 36 leads to 4 + 9 = 13 = b.

${\begin{aligned}6x^{2}+13x+6&={\frac {(6x+4)(6x+9)}{6}}\\&={\frac {2(3x+2)(3)(2x+3)}{6}}\\&=(3x+2)(2x+3)\end{aligned}}$

Factoring other polynomials

Sum/difference of two cubes

A visual representation of the factorization of cubes using volumes. For a sum of cubes, simply substitute z=-y.

Another formula for factoring is the sum or difference of two cubes. The sum can be represented by

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

and the difference by

$a^{3}-b^{3}=(a-b)(a^{2}+ab+b^{2}).\,\!$

Difference of two fourth powers

Another formula is the difference of two fourth powers, which is

$a^{4}-b^{4}=(a^{2}+b^{2})(a+b)(a-b).\,\!$

• This formula is derivable from the difference-of-two-squares formula by treating a⁴ and b⁴ as the squares of a² and b², respectively; applying the difference-of-two squares formula in factoring (a⁴ - b⁴) into ([a² + b²] · [a² - b²]); and reapplying the difference-of-two-squares formula to the second factor, thereby restating the overall expression as ([a² + b²] · [a + b] · [a - b]).

a⁴+4b⁴

Main article: Aurifeuillean factorization

Another formula for factoring is a⁴+4b⁴, which is

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

Sum/difference of two fifth powers

Another formula for factoring is the sum or difference of two fifth powers. The sum can be represented by

$a^{5}+b^{5}=(a+b)(a^{4}-a^{3}b+a^{2}b^{2}-ab^{3}+b^{4}),\,\!$

and the difference by

$a^{5}-b^{5}=(a-b)(a^{4}+a^{3}b+a^{2}b^{2}+ab^{3}+b^{4}).\,\!$

(Both of these can be factored further, but not with integer coefficients.)

Sum by difference of two sixth powers

Then there's the formula for factoring the sum or difference of two sixth powers. The sum can be represented by

$a^{6}+b^{6}=(a^{2}+b^{2})(a^{4}-a^{2}b^{2}+b^{4}),\,\!$

and the difference by

$a^{6}-b^{6}=(a+b)(a-b)(a^{2}-ab+b^{2})(a^{2}+ab+b^{2}).\,\!$

a⁶+27b⁶

Main article: Aurifeuillean factorization

Another formula for factoring is a⁶+27b⁶, which is

$a^{6}+27b^{6}=(a^{2}+3b^{2})(a^{2}-3ab+3b^{2})(a^{2}+3ab+3b^{2}).\,\!$

Sum/difference of two seventh powers

Then there’s the formula for factoring the sum or difference of two seventh powers. The sum can be represented by

$a^{7}+b^{7}=(a+b)(a^{6}-a^{5}b+a^{4}b^{2}-a^{3}b^{3}+a^{2}b^{4}-ab^{5}+b^{6}),\,\!$

and the difference by

$a^{7}-b^{7}=(a-b)(a^{6}+a^{5}b+a^{4}b^{2}+a^{3}b^{3}+a^{2}b^{4}+ab^{5}+b^{6}).\,\!$

Difference of two eighth powers

And lastly there's the formula for factoring the difference of two eighth powers, which is

$a^{8}-b^{8}=(a-b)(a+b)(a^{2}+b^{2})(a^{4}+b^{4}).\,\!$

($a^{4}+b^{4}$ can be factored further, but not with integer coefficients.)

Sum/difference of two n^th powers

The above factorization of differences of powers can be extended to any positive integer power n by use of the geometric series. By noting that

$x^{n-1}+x^{n-2}+\ldots +x+1={\frac {x^{n}-1}{x-1}},$

and multiplying by the (x − 1) factor, the desired result is found. To give the general form as above, we can replace x by a/b and multiply both sides by bⁿ. This gives the general form for the difference of two n^th powers as

$a^{n}-b^{n}=(a-b)(a^{n-1}+ba^{n-2}+b^{2}a^{n-3}+\ldots +b^{n-2}a+b^{n-1}).\!$

The corresponding sum of two n^th powers depends on whether n is even or odd. If n is odd, b can be replaced by −b in the above formula, to give

$a^{n}+b^{n}=(a+b)(a^{n-1}-ba^{n-2}+b^{2}a^{n-3}-\ldots -b^{n-2}a+b^{n-1}).\!$

If n is even, we consider two cases:

1. If n is a power of 2

$a^{n}+b^{n}\!$

is unfactorable.

2.Let n equal

$m\cdot 2^{k},m>1,k\neq 0\!$

where m is odd.

Then, the expression can be written

$a^{m\cdot 2^{k}}+b^{m\cdot 2^{k}}.\!$

Now, the general factorization is

$a^{n}+b^{n}=(a^{2^{k}}+b^{2^{k}})(a^{n-2^{k}}-a^{n-2\cdot 2^{k}}b^{2^{k}}+a^{n-3\cdot 2^{k}}b^{2\cdot 2^{k}}-\ldots -a^{2^{k}}b^{n-2\cdot 2^{k}}+b^{n-2^{k}})=(a^{2^{k}}+b^{2^{k}})\sum _{i=1}^{m}a^{(m-i)2^{k}}(-b^{2^{k}})^{i-1}.\!$

Other factorization formulae

$x^{3}+y^{3}+z^{3}-3xyz=(x+y+z)(x^{2}+y^{x}z-yz).\!$

Unique factorization domains

The integers and the polynomials over a field share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a unit, ±1 in the case of integers) and a product of irreducible 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 called unique factorization domains (UFD).

Greatest common divisors exist in UFDs, and conversely, every integral domain in which greatest common divisors exist is an UFD. Every principal ideal domain is an 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 F such that there cannot exist any factorization algorithm in the Euclidean domain F[x] of the univariate polynomials over F.

Ideals

Main article: Dedekind domain

In algebraic number theory, the study of Diophantine equations led mathematicians, during 19th century, to introduce generalizations of the integers called algebraic integers. The first ring of algebraic integers that have been considered were Gaussian integers and Eisenstein integers, which share with usual integers the property of being principal ideal domains, and have thus the 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 $\mathbb {Z} [{\sqrt {-5}}],$ in which

$9=3\cdot 3=(2+{\sqrt {-5}})(2-{\sqrt {-5}}),$

and all these factors are 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 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 Dedekind, who proved that the rings of algebraic integers have unique factorization of ideals: in these rings, every ideal is a product of prime ideals, and this factorization is unique up the order of the factors. The integral domains that have this unique factorization property are now called Dedekind domains. 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 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

• Euler's factorization method for integers
• Fermat's factorization method for integers
• Monoid factorisation
• Multiplicative partition
• Table of Gaussian integer factorizations

References

• 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
• Dickson, Leonard Eugene (1922), First Course in the Theory of Equations, New York: John Wiley & Sons
• Fite, William Benjamin (1921), College Algebra (Revised), Boston: D. C. Heath & Co.
• Klein, Felix (1925), Elementary Mathematics from an Advanced Standpoint; Arithmetic, Algebra, Analysis, Dover
• Selby, Samuel M., CRC Standard Mathematical Tables (18th ed.), The Chemical Rubber Co.

External links

• Wolfram Alpha can factorize too.