Editing Factorization (section)

{{Short description|(Mathematical) decomposition into a product}}
{{other uses|Factor (disambiguation)}}
[[File:Factorisatie.svg|thumb|right|The polynomial ''x''<sup>2</sup>&nbsp;+&nbsp;''cx''&nbsp;+&nbsp;''d'', where ''a&nbsp;+&nbsp;b&nbsp;=&nbsp;c'' and ''ab&nbsp;=&nbsp;d'', can be factorized into (''x&nbsp;+&nbsp;a'')(''x&nbsp;+&nbsp;b'').]]

In [[mathematics]], '''factorization''' (or '''factorisation''', see [[American and British English spelling differences#-ise, -ize (-isation, -ization)|English spelling differences]]) or '''factoring''' consists of writing a number or another [[mathematical object]] as a product of several ''[[Factor (arithmetic)|factors]]'', usually smaller or simpler objects of the same kind. For example, {{math|3 × 5}} is an ''[[integer factorization]]'' of {{math|15}}, and {{math|(''x'' − 2)(''x'' + 2)}} is a ''[[polynomial factorization]]'' of {{math|''x''<sup>2</sup> − 4}}.

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

''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]]. [[matrix (mathematics)|Matrices]] possess many kinds of [[matrix factorization]]s. For example, every matrix has a unique [[LU decomposition|LUP factorization]] as a product of a [[lower triangular matrix]] {{mvar|L}} with all diagonal entries equal to one, an [[upper triangular matrix]] {{mvar|U}}, and a [[permutation matrix]] {{mvar|P}}; this is a matrix formulation of [[Gaussian elimination]].