Factorization

In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, factorization (also factorisation in British English) or factoring is the decomposition of an object (for example, a number

Number

A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....

, a polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

, or a matrix

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

) into a product

Product (mathematics)

In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of multiplication...

 of other objects, or factors, which when multiplied

Multiplication

Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....

 together give the original. For example, the number 15 factors into primes

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 as 3 × 5, and the polynomial x² − 4 factors as (x − 2)(x + 2). In all cases, a product of simpler objects is obtained.

The aim of factoring is usually to reduce something to "basic building blocks," such as numbers to prime numbers, or polynomials to irreducible polynomial

Irreducible polynomial

In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....

s. Factoring integers is covered by the fundamental theorem of arithmetic

Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...

 and factoring polynomials

Polynomial factorization

In mathematics and computer algebra, polynomial factorization refers to factoring a polynomial into irreducible polynomials over a given field.-Formulation of the question:...

 by the fundamental theorem of algebra

Fundamental theorem of algebra

The fundamental theorem of algebra states that every non-constant single-variable polynomial with complex coefficients has at least one complex root...

. Viète's formulas relate the coefficients of a polynomial to its roots.

The opposite of polynomial factorization is expansion

Polynomial expansion

In mathematics, an expansion of a product of sums expresses it as a sum of products by using the fact that multiplication distributes over addition...

, the multiplying together of polynomial factors

Divisor

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

 to a "expanded" polynomial, written as just a sum of terms.

Integer factorization

Integer factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

 for large integers appears to be a difficult problem. There is no known method to carry it out quickly. Its complexity is the basis of the assumed security of some public key cryptography algorithms, such as RSA.

A matrix can also be factorized into a product of matrices of special types, for an application in which that form is convenient. One major example of this uses an orthogonal

Orthogonal matrix

In linear algebra, an orthogonal matrix , is a square matrix with real entries whose columns and rows are orthogonal unit vectors ....

 or unitary matrix, and a triangular matrix

Triangular matrix

In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where either all the entries below or all the entries above the main diagonal are zero...

. There are different types: QR decomposition

QR decomposition

In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...

, LQ, QL, RQ, RZ.

Another example is the factorization of a function

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 as the composition

Function composition

In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

 of other functions having certain properties; for example, every function can be viewed as the composition of a surjective function

Surjective function

In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

 with an injective function

Injective function

In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

. This situation is generalized by factorization system

Factorization system

In mathematics, it can be shown that every function can be written as the composite of a surjective function followed by an injective function. Factorization systems are a generalization of this situation in category theory.-Definition:...

s.

Integers

By the fundamental theorem of arithmetic

Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...

, every positive integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 greater than 1 has a unique prime factorization. Given an algorithm for integer factorization, one can factor any integer down to its constituent primes by repeated application of this algorithm. For very large numbers, no efficient algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 is known.

Quadratic polynomials

Any quadratic polynomial

Quadratic polynomial

In mathematics, a quadratic polynomial or quadratic is a polynomial of degree two, also called second-order polynomial. That means the exponents of the polynomial's variables are no larger than 2...

 over the complex numbers (polynomials of the form where , , and ∈ ) can be factored into an expression

Expression (mathematics)

In mathematics, an expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Symbols can designate numbers , variables, operations, functions, and other mathematical symbols, as well as punctuation, symbols of grouping, and other syntactic...

 with the form using the quadratic formula. The method is as follows:


where and are the two roots of the polynomial, found with the quadratic formula.

Polynomials factorable over the integers

where

and

You can then set each binomial equal to zero, and solve for x to reveal the two roots. Factoring does not involve any other formulas, and is mostly just something you see when you come upon a quadratic equation.

Take 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

Discriminant

In algebra, the discriminant of a polynomial is an expression which gives information about the nature of the polynomial's roots. For example, the discriminant of the quadratic polynomialax^2+bx+c\,is\Delta = \,b^2-4ac....

 that is a perfect square, that polynomial is factorable over the integers.

For example, look at the polynomial 2x² + 2x − 12. If you substitute the values of the expression 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 look at 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

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


and

Sum/difference of two squares

Another common type of algebraic factoring is called the difference of two squares

Difference of two squares

In mathematics, the difference of two squares, or the difference of perfect squares, is when a number is squared, or multiplied by itself, and is then subtracted from another squared number...

. It is the application of the formula


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


For example, can be factored into .

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



Group similar terms,

Factor out Greatest Common Factor,

Factor out binomial

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


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:

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

Sum/difference of two cubes

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

Difference of two fourth powers

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

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
and the difference by

Sum/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
and the difference by

Sum/difference of two seventh powers

And last there's the formula for factoring the sum or difference of two seventh powers. The sum can be represented by
and the difference by

Difference of n^th powers

This factorization can be extended to any positive integer power n by use of the geometric series. By noting that
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 bn.
This gives the general form for the difference of two n^th powers as
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. If n is even, the form is somewhat more
tedious.

See also

• Completing the square
  Completing the square
  In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the formax^2 + bx + c\,\!to the formIn this context, "constant" means not depending on x. The expression inside the parenthesis is of the form ...
  
  
• Factorization of polynomials
• Factor theorem
  Factor theorem
  In algebra, the factor theorem is a theorem linking factors and zeros of a polynomial. It is a special case of the polynomial remainder theorem.The factor theorem states that a polynomial f has a factor if and only if f=0....
  
  
• FOIL rule
  FOIL rule
  In elementary algebra, FOIL is a mnemonic for the standard method of multiplying two binomials—hence the method may be referred to as the FOIL method...
  
  
• Matrix decomposition
  Matrix decomposition
  In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. There are many different matrix decompositions; each finds use among a particular class of problems.- Example :...
  
  
• Pascal's triangle
  Pascal's triangle
  In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
  
  
• Prime factor
  Prime factor
  In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
  
  
• Program synthesis
  Program synthesis
  Program synthesis is a special form of automatic programming that is most often paired with a technique for formal verification. The goal is to automatically construct a program that provably satisfies a given high-level specification...
  
  
• Table of Gaussian integer factorizations
  Table of Gaussian integer factorizations
  Gaussian integers may be categorized as zero, the four units, Gaussian primes and composites. This is a list of Gaussian Integers in the first quadrant followed either by an explicit factorization or followed by a label for primes. The factorizations take the form of an optional unit multiplied...
  
  
• Unique factorization
  Unique factorization domain
  In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
  
  

External links

• One hundred million numbers factored on html pages.
• A page about factorization, Algebra, Factoring
• WIMS Factoris is an online factorization tool.
• Wolfram Alpha
  Wolfram Alpha
  Wolfram Alpha is an answer-engine developed by Wolfram Research. It is an online service that answers factual queries directly by computing the answer from structured data, rather than providing a list of documents or web pages that might contain the answer as a search engine might...
  
  can factorize too.