TheInfoList

In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, factorization (or factorisation, see
English spelling differences Despite the various English dialects spoken from country to country and within different regions of the same country, there are only slight regional variations in English orthography, the two most notable variations being British and America ...
) or factoring consists of writing a number or another
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs ...
as a product of several ''factors'', usually smaller or simpler objects of the same kind. For example, is a factorization of the
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
, and is a factorization of the
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

. Factorization is not usually considered meaningful within number systems possessing
division Division or divider may refer to: Mathematics *Division (mathematics), the inverse of multiplication *Division algorithm, a method for computing the result of mathematical division Military *Division (military), a formation typically consisting o ...
, such as the
real Real may refer to: * Reality Reality is the sum or aggregate of all that is real or existent within a system, as opposed to that which is only Object of the mind, imaginary. The term is also used to refer to the ontological status of things, ind ...
or
complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, every complex number can be expressed in the for ...

s, since any $x$ can be trivially written as $\left(xy\right)\times\left(1/y\right)$ whenever $y$ is not zero. However, a meaningful factorization for a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
or a
rational function In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

can be obtained by writing it in lowest terms and separately factoring its numerator and denominator. Factorization was first considered by
ancient Greek mathematicians Greek mathematics refers to mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geomet ...
in the case of integers. They proved the
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
, which asserts that every positive integer may be factored into a product of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique
up to Two mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is a ...
the order of the factors. Although
integer factorization In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Frie ...
is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the
RSA cryptosystem RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym An acronym is a word or name formed from the initial components of a longer name or p ...
to implement
public-key cryptography Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys KEYS (1440 AM broadcasting, AM) is a radio station serving the Corpus Christi, Texas, Corpus Christi, Texas area with a talk radio, talk ...
.
Polynomial factorization In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its
roots A root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a lar ...
to finding the roots of the factors. Polynomials with coefficients in the integers or in a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by
irreducible polynomial In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s. In particular, a
univariate polynomial In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
with
complex The UCL Faculty of Mathematical and Physical Sciences is one of the 11 constituent faculties of University College London , mottoeng = Let all come who by merit deserve the most reward , established = , type = Public university, Public rese ...

coefficients admits a unique (up to ordering) factorization into
linear polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
s: this is a version of the
fundamental theorem of algebra The fundamental theorem of algebra states that every non- constant single-variable polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, s ...
. In this case, the factorization can be done with
root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding Zero of a function, zeroes, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to ...
s. The case of polynomials with integer coefficients is fundamental for
computer algebra In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating expression (mathematics), ...
. There are efficient computer
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

s for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see
factorization of polynomials In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
). A
commutative ring In , a branch of , a commutative ring is a in which the multiplication operation is . The study of commutative rings is called . Complementarily, is the study of s where multiplication is not required to be commutative. Definition and first e ...
possessing the unique factorization property is called a
unique factorization domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. There are
number system A number is a mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deduc ...
s, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of
Dedekind domain In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathema ...
s:
ideals Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
factor uniquely into
prime ideal In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. ...
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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

with an
injective function In , an injective function (also known as injection, or one-to-one function) is a that maps elements to distinct elements; that is, implies . In other words, every element of the function's is the of one element of its . The term must no ...

.
Matrices Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics) In mathematics, a matrix (plural matrices) is a rectangle, rectangular ''wikt:array, array'' or ''table'' of numbers, symbol (formal), symbols, or expression (mathema ...
possess many kinds of
matrix factorization In the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population ...

s. For example, every matrix has a unique LUP factorization as a product of a
lower triangular matrix In the mathematics, mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if a ...
with all diagonal entries equal to one, an
upper triangular matrix In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
, and a
permutation matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

; this is a matrix formulation of Gaussian elimination.

# Integers

By the
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
, every
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
greater than 1 has a unique (up to the order of the factors) factorization into
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, which are those integers which cannot be further factorized into the product of integers greater than one. For computing the factorization of an integer , one needs an
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

for finding a
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

of or deciding that is prime. When such a divisor is found, the repeated application of this algorithm to the factors and gives eventually the complete factorization of . For finding a divisor of , if any, it suffices to test all values of such that and . In fact, if is a divisor of such that , then is a divisor of such that . If one tests the values of in increasing order, the first divisor that is found is necessarily a prime number, and the ''cofactor'' cannot have any divisor smaller than . For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of that is not smaller than and not greater than . There is no need to test all values of 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

. 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 Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French French (french: français(e), link=no) may refer to: * Something of, from, or related to France France (), officially the French Republic (fren ...

was unable to discover that the 6th
Fermat number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
: $1 + 2^ = 1 + 2^ = 4\,294\,967\,297$ is not a prime number. In fact, applying the above method would require more than , for a number that has 10
decimal digit , in order of value. A numerical digit is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent number A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label ...

s. 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 RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym An acronym is a word or name formed from the initial components of a longer name or p ...
, which is widely used for secure
internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a ''internetworking, network of networks'' that consist ...

communication.

## Example

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

# Expressions

Manipulating
expressions Expression may refer to: Linguistics * Expression (linguistics), a word, phrase, or sentence * Fixed expression, a form of words with a specific meaning * Idiom, a type of fixed expression * Metaphor#Common types, Metaphorical expression, a parti ...
is the basis of
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...

. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put an
equation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...

in a factored form , then the problem of solving the equation splits into two independent (and generally easier) problems and . 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 :$\left(x-a\right)\left(x-b\right)\left(x-c\right),$ with only two multiplications and three subtractions. Moreover, the factored form immediately gives
roots A root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a lar ...
''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^-1$ can be factored into two irreducible factors $x-1$ and $x^+x^+\cdots+x^2+x+1$. Various methods have been developed for finding factorizations; some are described
below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) *Less than *Temperatures below freezing *Hell or underworld People with the surname *Fred Below (1926–1988), American blues drummer *Fritz von Below (1853 ...
. Solving
algebraic equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
s may be viewed as a problem of polynomial factorization. In fact, the
fundamental theorem of algebra The fundamental theorem of algebra states that every non- constant single-variable polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, s ...
can be stated as follows: every
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

in of degree with
complex The UCL Faculty of Mathematical and Physical Sciences is one of the 11 constituent faculties of University College London , mottoeng = Let all come who by merit deserve the most reward , established = , type = Public university, Public rese ...

coefficients may be factorized into linear factors $x-a_i,$ for , where the s are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the s generally cannot be computed in terms of radicals (''n''th roots), by the
Abel–Ruffini theorem In mathematics, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) states that there is no solution in radicals to general algebraic equation, polynomial equations of quintic equation, degree five or higher with arbitrary coef ...
. In most cases, the best that can be done is computing approximate values of the roots with a
root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding Zero of a function, zeroes, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to ...
.

## History of factorization of expressions

The systematic use of algebraic manipulations for simplifying expressions (more specifically
equation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...

s)) may be dated to 9th century, with
al-Khwarizmi Muḥammad ibn Mūsā al-Khwārizmī ( fa, محمد بن موسی خوارزمی, Moḥammad ben Musā Khwārazmi; ), Arabized as al-Khwarizmi and formerly Latinized as ''Algorithmi'', was a Persian polymath A polymath ( el, πολυμα ...

's book ''
The Compendious Book on Calculation by Completion and Balancing ''The Compendious Book on Calculation by Completion and Balancing'' ( ar, ٱلْكِتَاب ٱلْمُخْتَصَر فِي حِسَاب ٱلْجَبْر وَٱلْمُقَابَلَة, ''al-Kitāb al-Mukhtaṣar fī Ḥisāb al-Jabr wal-Muqāb ...
'', which is titled with two such types of manipulation. However, even for solving
quadratic equation In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. ...

s, 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
monomial In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s, binomials, and
trinomial In elementary algebra, a trinomial is a polynomial consisting of three terms or monomials. Trinomial expressions # 3x + 5y + 8z with x, y, z variables # 3t + 9s^2 + 3y^3 with t, s, y variables # 3ts + 9t + 5s with t, s variables # A x^a y^b z^c + ...

s. Then, in a second section, he set up the equation , and showed that this matches the form of multiplication he had previously provided, giving the factorization .

## 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
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

s, though they also may be applied when the terms of the sum are not
monomial In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s, 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...

of these coefficients. For example, :$6x^3y^2 + 8x^4y^3 - 10x^5y^3 = 2x^3y^2\left(3 + 4xy -5x^2y\right),$ since 2 is the greatest common divisor of 6, 8, and 10, and $x^3y^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 , and the last two terms have the common factor . Thus : $4x^2+20x+3xy+15y = \left(4x^2+20x\right)+\left(3xy+15y\right) = 4x\left(x+5\right)+3y\left(x+5\right).$ Then a simple inspection shows the common factor , leading to the factorization : $4x^2+20x+3xy+15y = \left(4x+3y\right)\left(x+5\right).$ 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 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 : In elementary algebra Elementary algebra encompasses some of the basic concepts of algebra, one of the main branches of mathematics. It is typically taught to secondary school students and builds on their understanding of arithmetic. Whereas a ...

method for getting
quadratic formula In elementary algebra Elementary algebra encompasses some of the basic concepts of algebra, one of the main branches of mathematics. It is typically taught to secondary school students and builds on their understanding of arithmetic. Whereas a ...

. Another example is the factorization of $x^4 + 1.$ If one introduces the non-real square root of –1, commonly denoted , then one has a
difference of squares In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
:$x^4+1=\left(x^2+i\right)\left(x^2-i\right).$ However, one may also want a factorization with
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
coefficients. By adding and subtracting $2x^2,$ and grouping three terms together, one may recognize the square of a binomial: :$x^4+1 = \left(x^4+2x^2+1\right)-2x^2 = \left(x^2+1\right)^2 - \left\left(x\sqrt2\right\right)^2 =\left\left(x^2+x\sqrt2+1\right\right)\left\left(x^2-x\sqrt2+1\right\right).$ Subtracting and adding $2x^2$ also yields the factorization: :$x^4+1 = \left(x^4-2x^2+1\right)+2x^2 = \left(x^2-1\right)^2 + \left\left(x\sqrt2\right\right)^2 =\left\left(x^2+x\sqrt-1\right\right)\left\left(x^2-x\sqrt-1\right\right).$ These factorizations work not only over the complex numbers, but also over any
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
, where either –1, 2 or –2 is a square. In a
finite field In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, the product of two non-squares is a square; this implies that the
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

$x^4 + 1,$ which is irreducible over the integers, is reducible modulo every
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
. For example, :$x^4 + 1 \equiv \left(x+1\right)^4 \pmod 2;$ :$x^4 + 1 \equiv \left(x^2+x-1\right)\left(x^2-x-1\right) \pmod 3,\qquad$since $1^2 \equiv -2 \pmod 3;$ :$x^4 + 1 \equiv \left(x^2+2\right)\left(x^2-2\right) \pmod 5,\qquad$since $2^2 \equiv -1 \pmod 5;$ :$x^4 + 1 \equiv \left(x^2+3x+1\right)\left(x^2-3x+1\right) \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 and that appear in these identities may represent any subexpression of the expression that has to be factorized. *;
Difference of two squares In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

::$E^2 - F^2 = \left(E+F\right)\left(E-F\right)$ :For example, ::$\begin a^2 + &2ab + b^2 - x^2 +2xy - y^2 \\ &= \left(a^2 + 2ab + b^2\right) - \left(x^2 -2xy + y^2\right) \\ &= \left(a+b\right)^2 - \left(x -y\right)^2 \\ &= \left(a+b + x -y\right)\left(a+b -x + y\right). \end$ *;Sum/difference of two cubes ::$E^3 + F^3 = \left(E + F\right)\left(E^2 - EF + F^2\right)$ ::$E^3 - F^3 = \left(E - F\right)\left(E^2 + EF + F^2\right)$ *;Difference of two fourth powers ::$\begin E^4 - F^4 &= \left(E^2 + F^2\right)\left(E^2 - F^2\right) \\ &= \left(E^2 + F^2\right)\left(E + F\right)\left(E - F\right) \end$ *;Sum/difference of two th powers :In the following identities, the factors may often be further factorized: :*;Difference, even exponent ::$E^-F^= \left(E^n+F^n\right)\left(E^n-F^n\right)$ :*;Difference, even or odd exponent ::$E^n - F^n = \left(E-F\right)\left(E^ + E^F + E^F^2 + \cdots + EF^ + F^ \right)$ ::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 = \left(E+F\right)\left(E^ - E^F + E^F^2 - \cdots - EF^ + F^ \right)$ ::(obtained by changing by 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
(if and contain complex numbers, this may be not the case). If ''n'' has an odd divisor, that is if with odd, one may use the preceding formula (in "Sum, odd exponent") applied to $\left(E^q\right)^p+\left(F^q\right)^p.$ *;Trinomials and cubic formulas :::$\begin &x^2 + y^2 + z^2 + 2\left(xy +yz+xz\right)= \left(x + y+ z\right)^2 \\ &x^3 + y^3 + z^3 - 3xyz = \left(x + y + z\right)\left(x^2 + y^2 + z^2 - xy - xz - yz\right)\\ &x^3 + y^3 + z^3 + 3x^2\left(y + z\right) +3y^2\left(x+z\right) + 3z^2\left(x+y\right) + 6xyz = \left(x + y+z\right)^3 \\ &x^4 + x^2y^2 + y^4 = \left(x^2 + xy+y^2\right)\left(x^2 - xy + y^2\right). \end$ *;Binomial expansions :The
binomial theorem In elementary algebra Elementary algebra encompasses some of the basic concepts of algebra, one of the main branches of mathematics. It is typically taught to secondary school students and builds on their understanding of arithmetic. Whereas a ...
supplies patterns that can easily be recognized from the integers that appear in them :In low degree: ::$a^2 + 2ab + b^2 = \left(a + b\right)^2$ ::$a^2 - 2ab + b^2 = \left(a - b\right)^2$ ::$a^3 + 3a^2b + 3ab^2 + b^3 = \left(a+b\right)^3$ ::$a^3 - 3a^2b + 3ab^2 - b^3 = \left(a-b\right)^3$ :More generally, the coefficients of the expanded forms of $\left(a+b\right)^n$ and $\left(a-b\right)^n$ are the
binomial coefficient In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s, that appear in the th row of
Pascal's triangle In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
.

### Roots of unity

The th
roots of unity In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis) ...
are the
complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, every complex number can be expressed in the for ...

s each of which is a
root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a large grou ...
of the polynomial $x^n-1.$ They are thus the numbers :$e^=\cos \tfracn +i\sin \tfracn$ for $k=0, \ldots, n-1.$ It follows that for any two expressions and , one has: :$E^n-F^n= \left(E-F\right)\prod_^ \left\left(E-F e^\right\right)$ :$E^+F^=\prod_^ \left\left(E-F e^\right\right) \qquad \text n \text$ :$E^+F^=\left(E+F\right)\prod_^\left\left(E+F e^\right\right) \qquad \text n \text$ If and are real expressions, and one wants real factors, one has to replace every pair of
complex conjugate In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
factors by its product. As the complex conjugate of $e^$ is $e^,$ and :$\left\left(a-be^\right\right)\left\left(a-be^\right\right)= a^2-ab\left\left(e^+e^\right\right)+b^2e^e^= a^2-2ab\cos\,\alpha +b^2,$ one has the following real factorizations (one passes from one to the other by changing into or , and applying the usual trigonometric formulas: :$\beginE^-F^&= \left(E-F\right)\left(E+F\right)\prod_^ \left\left(E^2-2EF \cos\,\tfracn +F^2\right\right)\\ &=\left(E-F\right)\left(E+F\right)\prod_^ \left\left(E^2+2EF \cos\,\tfracn +F^2\right\right)\end$ :$\beginE^ + F^ &= \prod_^n \left\left(E^2 + 2EF\cos\,\tfrac+F^2\right\right)\\ &=\prod_^n \left\left(E^2 - 2EF\cos\,\tfrac+F^2\right\right) \end$ The
cosine In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in al ...

s that appear in these factorizations are
algebraic number An algebraic number is any complex number In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus ...
s, and may be expressed in terms of radicals (this is possible because their
Galois group In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
is cyclic); however, these radical expressions are too complicated to be used, except for low values of . For example, :$a^4 + b^4 = \left(a^2 - \sqrt 2 ab + b^2\right)\left(a^2 + \sqrt 2 ab + b^2\right).$ :$a^5 - b^5 = \left(a - b\right)\left\left(a^2 + \frac2 ab + b^2\right\right)\left\left(a^2 +\frac2 ab + b^2\right\right),$ :$a^5 + b^5 = \left(a + b\right)\left\left(a^2 - \frac2 ab + b^2\right\right)\left\left(a^2 -\frac2 ab + b^2\right\right),$ Often one wants a factorization with rational coefficients. Such a factorization involves
cyclotomic polynomial In mathematics, the ''n''th cyclotomic polynomial, for any positive integer ''n'', is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any Its root of a function, roots are al ...
s. To express rational factorizations of sums and differences or powers, we need a notation for the
homogenization of a polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
: if $P\left(x\right)=a_0x^n+a_ix^ +\cdots +a_n,$ its ''homogenization'' is the bivariate polynomial $\overline P\left(x,y\right)=a_0x^n+a_ix^y +\cdots +a_ny^n.$ Then, one has :$E^n-F^n=\prod_\overline Q_n\left(E,F\right),$ :$E^n+F^n=\prod_\overline Q_n\left(E,F\right),$ where the products are taken over all divisors of , or all divisors of that do not divide , and $Q_n\left(x\right)$ is the th cyclotomic polynomial. For example, :$a^6-b^6= \overline Q_1\left(a,b\right)\overline Q_2\left(a,b\right)\overline Q_3\left(a,b\right)\overline Q_6\left(a,b\right)=\left(a-b\right)\left(a+b\right)\left(a^2-ab+b^2\right)\left(a^2+ab+b^2\right),$ :$a^6+b^6=\overline Q_4\left(a,b\right)\overline Q_\left(a,b\right) = \left(a^2+b^2\right)\left(a^4-a^2b^2+b^4\right),$ 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

For polynomials, factorization is strongly related with the problem of solving
algebraic equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
s. An algebraic equation has the form :$P\left(x\right)\ \,\stackrel\ \,a_0x^n+a_1x^+\cdots+a_n=0,$ where is a polynomial in with $a_0\ne 0.$ A solution of this equation (also called a
root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a large grou ...
of the polynomial) is a value of such that :$P\left(r\right)=0.$ If $P\left(x\right)=Q\left(x\right)R\left(x\right)$ is a factorization of as a product of two polynomials, then the roots of are the union of the roots of and the roots of . Thus solving is reduced to the simpler problems of solving and . Conversely, the
factor theorem In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
asserts that, if is a root of , then may be factored as :$P\left(x\right)=\left(x-r\right)Q\left(x\right),$ where is the quotient of
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of division (mathematics), dividing one integer (the dividend) by another (the divisor), in a way that produces a quotient and a remainder smaller than the divisor ...
of by the linear (degree one) factor . If the coefficients of are
real Real may refer to: * Reality Reality is the sum or aggregate of all that is real or existent within a system, as opposed to that which is only Object of the mind, imaginary. The term is also used to refer to the ontological status of things, ind ...
or
complex The UCL Faculty of Mathematical and Physical Sciences is one of the 11 constituent faculties of University College London , mottoeng = Let all come who by merit deserve the most reward , established = , type = Public university, Public rese ...

numbers, the
fundamental theorem of algebra The fundamental theorem of algebra states that every non- constant single-variable polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, s ...
asserts that has a real or complex root. Using the factor theorem recursively, it results that :$P\left(x\right)=a_0\left(x-r_1\right)\cdots \left(x-r_n\right),$ where $r_1, \ldots, r_n$ are the real or complex roots of , with some of them possibly repeated. This complete factorization is unique
up to Two mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is a ...
the order of the factors. If the coefficients of 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 is a non-real root of , then its
complex conjugate In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
is also a root of . So, the product :$\left(x-r\right)\left(x-s\right) = x^2-\left(r+s\right)x+rs =x^2+2ax+a^2+b^2$ is a factor of 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 In mathematics and computing, a root-finding algorithm is an algorithm for finding Zero of a function, zeroes, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to ...
s. In practice, most algebraic equations of interest have
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
or
rational Rationality is the quality or state of being rational – that is, being based on or agreeable to reason Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογι ...
coefficients, and one may want a factorization with factors of the same kind. The
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
may be generalized to this case, stating that polynomials with integer or rational coefficients have the unique factorization property. More precisely, every polynomial with rational coefficients may be factorized in a product :$P\left(x\right)=q\,P_1\left(x\right)\cdots P_k\left(x\right),$ where is a rational number and $P_1\left(x\right), \ldots, P_k\left(x\right)$ are non-constant polynomials with integer coefficients that are irreducible and
primitive Primitive may refer to: Mathematics * Primitive element (field theory) * Primitive element (finite field) * Primitive cell (crystallography) * Primitive notion, axiomatic systems * Primitive polynomial (disambiguation), one of two concepts * Primit ...
; this means that none of the $P_i\left(x\right)$ 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 In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

s for computing this factorization, which are implemented in most
computer algebra In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating expression (mathematics), ...
systems. See
Factorization of polynomials In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
. 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

Every polynomial with
rational Rationality is the quality or state of being rational – that is, being based on or agreeable to reason Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογι ...
coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which is
primitive Primitive may refer to: Mathematics * Primitive element (field theory) * Primitive element (finite field) * Primitive cell (crystallography) * Primitive notion, axiomatic systems * Primitive polynomial (disambiguation), one of two concepts * Primit ...
(that is, the
greatest common divisor In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...

of the coefficients is 1), and has a positive leading coefficient (coefficient of the term of the highest degree). For example: :$-10x^2 + 5x + 5 = \left(-5\right)\cdot \left(2x^2 - x - 1\right)$ :$\fracx^5 + \frac x^2 + 2x + 1 = \frac \left( 2x^5 + 21x^2 + 12x + 6\right)$ In this factorization, the rational number is called the
content Content or contents may refer to: Media * Content (media), information or experience provided to audience or end-users by publishers or media producers ** Content industry, an umbrella term that encompasses companies owning and providing mass m ...
, 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 of a polynomial with integer coefficients. Then one divides out the greater common divisor of the coefficients of this polynomial for getting the primitive part, the content being $p/q.$ Finally, if needed, one changes the signs of 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 In number theory, two integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number that can be written without a Fraction (mathematics), fractional component. For example, 21, 4, 0, ...
denominators), but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.

## Using the factor theorem

The factor theorem states that, if is a
root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a large grou ...
of a
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

:$P\left(x\right)=a_0x^n+a_1x^+\cdots+a_x+a_n,$ meaning , then there is a factorization :$P\left(x\right)=\left(x-r\right)Q\left(x\right),$ where :$Q\left(x\right)=b_0x^+\cdots+b_x+b_,$ with $a_0=b_0$. Then
polynomial long division In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
or
synthetic division In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
give: :$b_i=a_0r^i +\cdots+a_r+a_i \ \text\ i = 1,\ldots,n1.$ This may be useful when one knows or can guess a root of the polynomial. For example, for $P\left(x\right) = x^3 - 3x + 2,$ one may easily see that the sum of its coefficients is 0, so is a root. As , and $r^2 +0r-3=-2,$ one has :$x^3 - 3x + 2 = \left(x - 1\right)\left(x^2 + x - 2\right).$

## Rational roots

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 In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is d ...

. If $x=\tfrac pq$ is a rational root of such a polynomial :$P\left(x\right)=a_0x^n+a_1x^+\cdots+a_x+a_n,$ the factor theorem shows that one has a factorization :$P\left(x\right)=\left(qx-p\right)Q\left(x\right),$ where both factors have integer coefficients (the fact that has integer coefficients results from the above formula for the quotient of by $x-p/q$). Comparing the coefficients of degree and the constant coefficients in the above equality shows that, if $\tfrac pq$ is a rational root in
reduced formIn statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, industrial, or social problem, it is conventional to begin with a ...
, then is a divisor of $a_0,$ and is a divisor of $a_n.$ Therefore, there is a finite number of possibilities for and , which can be systematically examined. For example, if the polynomial :$P\left(x\right)=2x^3 - 7x^2 + 10x - 6$ has a rational root $\tfrac pq$ with , then must divide 6; that is $p\in\,$ and must divide 2, that is $q\in\.$ Moreover, if , all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have :$\tfrac pq \in \.$ A direct computation shows that only $\tfrac 32$ is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization $2x^3 - 7x^2 + 10x - 6 = \left(2x -3\right)\left(x^2 -2x + 2\right).$

The above method may be adapted for
quadratic polynomial In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
s, leading to the ''ac method'' of factorization. Consider the quadratic polynomial :$P\left(x\right)=ax^2 + bx + c$ with integer coefficients. If it has a rational root, its denominator must divide evenly and it may be written as a possibly reducible fraction $r_1 = \tfrac ra.$ By
Vieta's formulas In mathematics, Vieta's formulas are formulas that relate the coefficients of a polynomial to sums and products of its Root of a function, roots. Named after François Viète (more commonly referred to by the Latinised form of his name, "Franciscu ...
, the other root $r_2$ is :$r_2 = -\frac ba - r_1 = -\frac ba-\frac ra =-\fraca = \frac sa,$ with $s=-\left(b+r\right).$ Thus the second root is also rational, and Vieta's second formula $r_1 r_2=\frac ca$ gives :$\frac sa\frac ra =\frac ca,$ that is :$rs=ac\quad \text\quad r+s=-b.$ Checking all pairs of integers whose product is gives the rational roots, if any. In summary, if $ax^2 +bx+c$ has rational roots there are integers and such $rs=ac$ and $r+s=-b$ (a finite number of cases to test), and the roots are $\tfrac ra$ and $\tfrac sa.$ In other words, one has the factorization :$a\left(ax^2+bx+c\right) = \left(ax-r\right)\left(ax-s\right).$ For example, let consider the quadratic polynomial :$6x^2 + 13x + 6.$ Inspection of the factors of leads to , giving the two roots :$r_1 = -\frac 46 =-\frac 23 \quad \text \quad r_2 = -\frac96 = -\frac 32,$ and the factorization :$6x^2 + 13x + 6 = 6\left(x+\tfrac 23\right)\left(x+\tfrac 32\right)= \left(3x+2\right)\left(2x+3\right).$

## Using formulas for polynomial roots

Any univariate
quadratic polynomial In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
$ax^2+bx+c$ can be factored using the
quadratic formula In elementary algebra Elementary algebra encompasses some of the basic concepts of algebra, one of the main branches of mathematics. It is typically taught to secondary school students and builds on their understanding of arithmetic. Whereas a ...

: :$ax^2 + bx + c = a\left(x - \alpha\right)\left(x - \beta\right) = a\left\left(x - \frac\right\right) \left\left(x - \frac\right\right),$ where $\alpha$ and $\beta$ are the two
roots A root In vascular plant Vascular plants (from Latin ''vasculum'': duct), also known as Tracheophyta (the tracheophytes , from Greek τραχεῖα ἀρτηρία ''trācheia artēria'' 'windpipe' + φυτά ''phutá'' 'plants'), form a lar ...
of the polynomial. If are all
real Real may refer to: * Reality Reality is the sum or aggregate of all that is real or existent within a system, as opposed to that which is only Object of the mind, imaginary. The term is also used to refer to the ontological status of things, ind ...
, the factors are real if and only if the
discriminant In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
$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 Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
of
characteristic Characteristic (from the Greek word for a property, attribute or trait Trait may refer to: * Phenotypic trait in biology, which involve genes and characteristics of organisms * Trait (computer programming), a model for structuring object-oriented ...
different from two, and, in particular, for coefficients in a
finite field In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
with an odd number of elements. There are also formulas for roots of
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system 200px, A network ...

and polynomials, which are, in general, too complicated for practical use. The
Abel–Ruffini theorem In mathematics, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) states that there is no solution in radicals to general algebraic equation, polynomial equations of quintic equation, degree five or higher with arbitrary coef ...
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 In , Galois theory, originally introduced by , provides a connection between and . This connection, the , allows reducing certain problems in field theory to group theory, which makes them simpler and easier to understand. Galois introduced the ...
is based on a systematic study of the relations between roots and coefficients, that include
Vieta's formulas In mathematics, Vieta's formulas are formulas that relate the coefficients of a polynomial to sums and products of its Root of a function, roots. Named after François Viète (more commonly referred to by the Latinised form of his name, "Franciscu ...
. Here, we consider the simpler case where two roots $x_1$ and $x_2$ of a polynomial $P\left(x\right)$ satisfy the relation :$x_2=Q\left(x_1\right),$ where is a polynomial. This implies that $x_1$ is a common root of $P\left(Q\left(x\right)\right)$ and $P\left(x\right).$ Its is therefore a root of the
greatest common divisor In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
of these two polynomials. It follows that this greatest common divisor is a non constant factor of $P\left(x\right).$ Euclidean algorithm for polynomials allows computing this greatest common factor. For example, if one know or guess that: $P\left(x\right)=x^3 -5x^2 -16x +80$ has two roots that sum to zero, one may apply Euclidean algorithm to $P\left(x\right)$ and $P\left(-x\right).$ The first division step consists in adding $P\left(x\right)$ to $P\left(-x\right),$ giving the
remainder In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
of :$-10\left(x^2-16\right).$ Then, dividing $P\left(x\right)$ by $x^2-16$ gives zero as a new remainder, and as a quotient, leading to the complete factorization :$x^3 - 5x^2 - 16x + 80 = \left(x -5\right)\left(x-4\right)\left(x+4\right).$

# Unique factorization domains

The integers and the polynomials over a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a
unit Unit may refer to: Arts and entertainment * UNIT, a fictional military organization in the science fiction television series ''Doctor Who'' * Unit of action, a discrete piece of action (or beat) in a theatrical presentation Music * Unit (album), ...
, ±1 in the case of integers) and a product of
irreducible elementIn abstract algebra, a non-zero non-unit Unit may refer to: Arts and entertainment * UNIT, a fictional military organization in the science fiction television series ''Doctor Who'' * Unit of action, a discrete piece of action (or beat) in a theatri ...
s (
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, in the case of integers), and this factorization is unique up to rearranging the factors and shifting units among the factors.
Integral domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
unique factorization domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s (UFD).
Greatest common divisor In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...

s exist in UFDs, and conversely, every integral domain in which greatest common divisors exist is an UFD. Every
principal ideal domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
is an UFD. A
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a #Definition, Euclidean function which allows a suitable generalization of the Euclidean division of ...
is an integral domain on which is defined a
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of division (mathematics), dividing one integer (the dividend) by another (the divisor), in a way that produces a quotient and a remainder smaller than the divisor ...
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 In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
such that there cannot exist any factorization algorithm in the Euclidean domain of the univariate polynomials over .

# Ideals

In
algebraic number theory Title page of the first edition of Disquisitiones Arithmeticae, one of the founding works of modern algebraic number theory. Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, ...
, the study of
Diophantine equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
s led mathematicians, during 19th century, to introduce generalizations of the
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s called
algebraic integer In algebraic number theory Title page of the first edition of Disquisitiones Arithmeticae, one of the founding works of modern algebraic number theory. Algebraic number theory is a branch of number theory that uses the techniques of abstrac ...
s. The first
ring of algebraic integers In algebraic number theory, an algebraic integer is a complex number that is a root of a function, root of some monic polynomial (a polynomial whose leading coefficient is 1) with coefficients in (the set of integers). The set of all algebraic i ...
that have been considered were
Gaussian integer In , a Gaussian integer is a whose real and imaginary parts are both s. The Gaussian integers, with ordinary and of s, form an , usually written as . This integral domain is a particular case of a of s. It does not have a ing that respects ari ...
s and
Eisenstein integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s, which share with usual integers the property of being
principal ideal domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
s, 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$ in which :$9=3\cdot 3 = \left(2+\sqrt\right)\left(2-\sqrt\right),$ 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 In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number ...
(probably including ''"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 Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
: in these rings, every ideal is a product of
prime ideal In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. ...
s, and this factorization is unique up the order of the factors. The
integral domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s that have this unique factorization property are now called
Dedekind domain In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathema ...
s. 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 Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryoti ...
as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the
LU decompositionIn numerical analysis (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 is four sexagesimal figures, which is about six decimal figures. 1 + 24/60 + 51/602 + 10/603 = 1.41421296... Numerical analysis is the study of al ...
gives a matrix as the product of a
lower triangular matrix In the mathematics, mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if a ...
by an
upper triangular matrix In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
. As this is not always possible, one generally considers the "LUP decomposition" having a
permutation matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

as its third factor. See
Matrix decomposition Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics) In mathematics, a matrix (plural matrices) is a rectangle, rectangular ''wikt:array, array'' or ''table'' of numbers, symbol (formal), symbols, or expression (mathema ...
for the most common types of matrix factorizations. A
logical matrixA logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix is a matrix with entries from the Boolean domain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number ...
represents a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of elem ...
, and
matrix multiplication In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

corresponds to
composition of relations In the of s, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the , the composition of relations is called relative multiplication, and its result is called a relative produc ...
. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a difunctional relation.

*
Euler's factorization methodEuler Leonhard Euler ( ; ; 15 April 170718 September 1783) was a Swiss mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topi ...
for integers * Fermat's factorization method for integers * Monoid factorisation *
Multiplicative partitionIn number theory, a multiplicative partition or unordered factorization of an integer ''n'' is a way of writing ''n'' as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors. Th ...
*Table of Gaussian integer factorizations

* * * * *