HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another
mathematical object A mathematical object is an abstract concept arising in mathematics. Typically, a mathematical object can be a value that can be assigned to a Glossary of mathematical symbols, symbol, and therefore can be involved in formulas. Commonly encounter ...
as a product of several '' factors'', usually smaller or simpler objects of the same kind. For example, is an ''
integer factorization In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
'' of , and is a ''
polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same doma ...
'' of . Factorization is not usually considered meaningful within number systems possessing division, such as the real or
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
s, since any x can be trivially written as (xy)\times(1/y) whenever y is not zero. However, a meaningful factorization for a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
or a
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be ...
can be obtained by writing it in lowest terms and separately factoring its numerator and denominator. Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 is prime or can be represented uniquely as a product of prime numbers, ...
, 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 object, mathematical objects and are called "equal up to an equivalence relation " * if and are related by , that is, * if holds, that is, * if the equivalence classes of and with respect to are equal. This figure of speech ...
the order of the factors. Although
integer factorization In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the
RSA cryptosystem The RSA (Rivest–Shamir–Adleman) cryptosystem is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
to implement
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
.
Polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same doma ...
has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...
to finding the roots of the factors. Polynomials with coefficients in the integers or in a field possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted f ...
s. In particular, a
univariate polynomial In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer ...
with
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
coefficients admits a unique (up to ordering) factorization into
linear polynomial In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer ...
s: this is a version of the
fundamental theorem of algebra The fundamental theorem of algebra, also called d'Alembert's theorem or the d'Alembert–Gauss theorem, states that every non-constant polynomial, constant single-variable polynomial with Complex number, complex coefficients has at least one comp ...
. In this case, the factorization can be done with
root-finding algorithm In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor ...
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 mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see
factorization of polynomials In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same doma ...
). A
commutative ring In mathematics, a commutative ring is a Ring (mathematics), ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring prope ...
possessing the unique factorization property is called a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. There are
number system A number is a mathematical object used to count, measure, and label. The most basic examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can ...
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 mathematics, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily un ...
s: ideals factor uniquely into
prime ideal In algebra, a prime ideal is a subset of a ring (mathematics), ring that shares many important properties of a prime number in the ring of Integer#Algebraic properties, integers. The prime ideals for the integers are the sets that contain all th ...
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, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a ...
with an
injective function In mathematics, an injective function (also known as injection, or one-to-one function ) is a function that maps distinct elements of its domain to distinct elements of its codomain; that is, implies (equivalently by contraposition, impl ...
.
Matrices Matrix (: matrices or matrixes) 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 ...
possess many kinds of
matrix factorization In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...
s. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix with all diagonal entries equal to one, an
upper triangular matrix In mathematics, 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 all the entries ''below'' the main diagonal are ...
, and a
permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...
; this is a matrix formulation of
Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
.


Integers

By the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 is prime or can be represented uniquely as a product of prime numbers, ...
, every
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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 mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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 divisibl ...
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, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite number, composite (i.e., not prime) the multiples of each prime, starting with ...
. 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 (; ; 17 August 1601 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he is recognized for his d ...
was unable to discover that the 6th
Fermat number In mathematics, a Fermat number, named after Pierre de Fermat (1601–1665), the first known to have studied them, is a natural number, positive integer of the form:F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers ...
: 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 A numerical digit (often shortened to just digit) or numeral is a single symbol used alone (such as "1"), or in combinations (such as "15"), to represent numbers in positional notation, such as the common base 10. The name "digit" originate ...
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 The RSA (Rivest–Shamir–Adleman) cryptosystem is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
, which is widely used for secure
internet The Internet (or internet) is the Global network, 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 ...
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 is the basis of
algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...
. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put an
equation In mathematics, an equation is a mathematical formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for ...
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 :(x-a)(x-b)(x-c), with only two multiplications and three subtractions. Moreover, the factored form immediately gives
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...
''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 * Ernst von Below (1863–1955), German World War I general * Fred Belo ...
. Solving
algebraic equation In mathematics, an algebraic equation or polynomial equation is an equation of the form P = 0, where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For example, x^5-3x+1=0 is an algebraic equati ...
s may be viewed as a problem of
polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same doma ...
. In fact, the
fundamental theorem of algebra The fundamental theorem of algebra, also called d'Alembert's theorem or the d'Alembert–Gauss theorem, states that every non-constant polynomial, constant single-variable polynomial with Complex number, complex coefficients has at least one comp ...
can be stated as follows: every
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
in of degree with
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
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 polynomial equations of degree five or higher with arbitrary coefficients. Here, ''general'' means t ...
. In most cases, the best that can be done is computing approximate values of the roots with a
root-finding algorithm In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor ...
.


History of factorization of expressions

The systematic use of algebraic manipulations for simplifying expressions (more specifically
equation In mathematics, an equation is a mathematical formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for ...
s) may be dated to 9th century, with
al-Khwarizmi Muhammad ibn Musa al-Khwarizmi , or simply al-Khwarizmi, was a mathematician active during the Islamic Golden Age, who produced Arabic-language works in mathematics, astronomy, and geography. Around 820, he worked at the House of Wisdom in B ...
's book ''
The Compendious Book on Calculation by Completion and Balancing ''The Concise Book of Calculation by Restoration and Balancing'' (, ;} or ), commonly abbreviated ''Al-Jabr'' or ''Algebra'' (Arabic: ), is an Arabic mathematics, Arabic mathematical treatise on algebra written in Baghdad around 820 by the Pers ...
'', which is titled with two such types of manipulation. However, even for solving
quadratic equation In mathematics, a quadratic equation () is an equation that can be rearranged in standard form as ax^2 + bx + c = 0\,, where the variable (mathematics), variable represents an unknown number, and , , and represent known numbers, where . (If and ...
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, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called a power product or primitive monomial, is a product of powers of variables with n ...
s,
binomial Binomial may refer to: In mathematics *Binomial (polynomial), a polynomial with two terms *Binomial coefficient, numbers appearing in the expansions of powers of binomials *Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition * ...
s, and
trinomial In elementary algebra, a trinomial is a polynomial consisting of three terms or monomials. Examples of 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 ...
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, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s, though they also may be applied when the terms of the sum are not
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called a power product or primitive monomial, is a product of powers of variables with n ...
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, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary ...
allows factoring out this common factor. If there are several such common factors, it is preferable to divide out the greatest such common factor. Also, if there are integer coefficients, one may factor out the
greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
of these coefficients. For example, 6 x^3 y^2 + 8 x^4 y^3 - 10 x^5 y^3 = 2 x^3 y^2(3 + 4xy - 5 x^2 y), 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 = (4x^2+20x) + (3xy+15y) = 4x(x+5) + 3y(x+5). Then a simple inspection shows the common factor , leading to the factorization 4x^2+20x+3xy+15y = (4x+3y) (x+5). In general, this works for sums of 4 terms that have been obtained as the product of two binomials. Although not frequently, this may work also for more complicated examples.


Adding and subtracting terms

Sometimes, some term grouping reveals part of a recognizable pattern. It is then useful to add and subtract terms to complete the pattern. A typical use of this is the
completing the square In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the form to the form for some values of and . In terms of a new quantity , this expression is a quadratic polynomial with no linear term. By s ...
method for getting the
quadratic formula In elementary algebra, the quadratic formula is a closed-form expression describing the solutions of a quadratic equation. Other ways of solving quadratic equations, such as completing the square, yield the same solutions. Given a general quadr ...
. 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 elementary algebra, a difference of two squares is one square (algebra), squared number (the number multiplied by itself) subtraction, subtracted from another squared number. Every difference of squares may be Factorization, factored as the Mult ...
x^4+1=(x^2+i)(x^2-i). However, one may also want a factorization with
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
coefficients. By adding and subtracting 2x^2, and grouping three terms together, one may recognize the square of a
binomial Binomial may refer to: In mathematics *Binomial (polynomial), a polynomial with two terms *Binomial coefficient, numbers appearing in the expansions of powers of binomials *Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition * ...
: x^4+1 = (x^4+2x^2+1) - 2x^2 = (x^2+1)^2 - \left(x\sqrt2\right)^2 = \left(x^2+x\sqrt2+1\right) \left(x^2-x\sqrt2+1\right). Subtracting and adding 2x^2 also yields the factorization: x^4+1 = (x^4-2x^2+1)+2x^2 = (x^2-1)^2 + \left(x\sqrt2\right)^2 = \left(x^2+x\sqrt-1\right) \left(x^2-x\sqrt-1\right). These factorizations work not only over the complex numbers, but also over any field, where either –1, 2 or –2 is a square. In a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, the product of two non-squares is a square; this implies that the
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
x^4 + 1, which is irreducible over the integers, is reducible
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
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 (x+1)^4 \pmod 2; x^4 + 1 \equiv (x^2+x-1)(x^2-x-1) \pmod 3,since 1^2 \equiv -2 \pmod 3; x^4 + 1 \equiv (x^2+2)(x^2-2) \pmod 5,since 2^2 \equiv -1 \pmod 5; x^4 + 1 \equiv (x^2+3x+1)(x^2-3x+1) \pmod 7,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 elementary algebra, a difference of two squares is one squared number (the number multiplied by itself) subtracted from another squared number. Every difference of squares may be factored as the product of the sum of the two numbers and the ...
:: E^2 - F^2 = (E+F)(E-F) :For example, :::\begin a^2 + &2ab + b^2 - x^2 +2xy - y^2 \\ &= (a^2 + 2ab + b^2) - (x^2 -2xy + y^2) \\ &= (a+b)^2 - (x -y)^2 \\ &= (a+b + x -y)(a+b -x + y). \end *;Sum/difference of two cubes :: E^3 + F^3 = (E + F)(E^2 - EF + F^2) :: E^3 - F^3 = (E - F)(E^2 + EF + F^2) :*;
Cauchy Baron Augustin-Louis Cauchy ( , , ; ; 21 August 1789 – 23 May 1857) was a French mathematician, engineer, and physicist. He was one of the first to rigorously state and prove the key theorems of calculus (thereby creating real a ...
identity ::: a^3 + b^3 + 3ab(a+b) = (a+b)^3 ::: a^3 - b^3 - 3ab(a-b) = (a-b)^3 *;Difference of two fourth powers ::\begin E^4 - F^4 &= (E^2 + F^2)(E^2 - F^2) \\ &= (E^2 + F^2)(E + F)(E - F) \end *;Sum/difference of two th powers :In the following identities, the factors may often be further factorized: :*;Difference, even exponent ::E^-F^= (E^n+F^n)(E^n-F^n) :*;Difference, even or odd exponent :: E^n - F^n = (E-F)(E^ + E^F + E^F^2 + \cdots + EF^ + F^ ) ::This is an example showing that the factors may be much larger than the sum that is factorized. :*;Sum, odd exponent :: E^n + F^n = (E+F)(E^ - E^F + E^F^2 - \cdots - EF^ + F^ ) ::(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, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...
(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 (E^q)^p+(F^q)^p. *;Trinomials and cubic formulas ::: \begin &x^2 + y^2 + z^2 + 2(xy +yz+xz)= (x + y+ z)^2 \\ &x^3 + y^3 + z^3 - 3xyz = (x + y + z)(x^2 + y^2 + z^2 - xy - xz - yz)\\ &x^3 + y^3 + z^3 + 3x^2(y + z) +3y^2(x+z) + 3z^2(x+y) + 6xyz = (x + y+z)^3 \\ &x^3 + y^3 + z^3 + 3(x + y)(y + z)(x + z) = (x + y + z)^3 \\ \end :*; Argand identity ::: x^4 + x^2y^2 + y^4 = (x^2 + xy +y^2)(x^2 - xy + y^2) ::: x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1) *;Binomial expansions :The
binomial theorem In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, the power expands into a polynomial with terms of the form , where the exponents and a ...
supplies patterns that can easily be recognized from the integers that appear in them :In low degree: :: a^2 + 2ab + b^2 = (a + b)^2 :: a^2 - 2ab + b^2 = (a - b)^2 :: a^3 + 3a^2b + 3ab^2 + b^3 = (a+b)^3 :: a^3 - 3a^2b + 3ab^2 - b^3 = (a-b)^3 :More generally, the coefficients of the expanded forms of (a+b)^n and (a-b)^n are the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s, that appear in the th row of
Pascal's triangle In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Bla ...
.


Roots of unity

The th
roots of unity In mathematics, a root of unity is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group char ...
are the
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
s each of which is a
root In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
of the polynomial x^n-1. They are thus the numbers e^ = \cos \tfracn + i\sin \tfrac n for k=0, \ldots, n-1. It follows that for any two expressions and , one has: E^n-F^n = (E-F) \prod_^ \left(E-F e^\right) E^n + F^n = \prod_^ \left(E-F e^\right) \qquad \text n \text E^+F^=(E+F) \prod_^\left(E+F e^\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, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, if a and b are real numbers, then the complex conjugate of a + bi is a - ...
factors by its product. As the complex conjugate of e^ is e^, and \left(a-be^\right) \left(a-be^\right)= a^2 - ab\left(e^+e^\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: \begin E^-F^&= (E-F)(E+F)\prod_^ \left(E^2-2EF \cos\,\tfracn +F^2\right)\\ &=(E-F)(E+F)\prod_^ \left(E^2+2EF \cos\,\tfracn +F^2\right) \end \begin E^ + F^ &= \prod_^n \left(E^2 + 2EF\cos\,\tfrac+F^2\right)\\ &=\prod_^n \left(E^2 - 2EF\cos\,\tfrac+F^2\right) \end The
cosine In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side opposite that ...
s that appear in these factorizations are
algebraic number In mathematics, an algebraic number is a number that is a root of a function, root of a non-zero polynomial in one variable with integer (or, equivalently, Rational number, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is ...
s, and may be expressed in terms of
radicals Radical (from Latin: ', root) may refer to: Politics and ideology Politics *Classical radicalism, the Radical Movement that began in late 18th century Britain and spread to continental Europe and Latin America in the 19th century *Radical politics ...
(this is possible because their
Galois group In mathematics, in the area of abstract algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension. The study of field extensions and their relationship to the pol ...
is cyclic); however, these radical expressions are too complicated to be used, except for low values of . For example, a^4 + b^4 = (a^2 - \sqrt 2 ab + b^2)(a^2 + \sqrt 2 ab + b^2). a^5 - b^5 = (a - b) \left(a^2 + \frac2 ab + b^2\right) \left(a^2 +\frac2 ab + b^2\right), a^5 + b^5 = (a + b) \left(a^2 - \frac2 ab + b^2\right) \left(a^2 -\frac2 ab + b^2\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 roots are all ''n''th prim ...
s. To express rational factorizations of sums and differences or powers, we need a notation for the
homogenization of a polynomial In mathematics, a homogeneous polynomial, sometimes called wikt:quantic, quantic in older texts, is a polynomial whose nonzero terms all have the same Degree of a polynomial, degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous poly ...
: if P(x)=a_0x^n+a_ix^ +\cdots +a_n, its ''homogenization'' is the bivariate polynomial \overline P(x,y)=a_0x^n+a_ix^y +\cdots +a_ny^n. Then, one has E^n-F^n=\prod_\overline Q_n(E,F), E^n+F^n=\prod_\overline Q_n(E,F), where the products are taken over all divisors of , or all divisors of that do not divide , and Q_n(x) is the th cyclotomic polynomial. For example, a^6-b^6= \overline Q_1(a,b)\overline Q_2(a,b)\overline Q_3(a,b)\overline Q_6(a,b)=(a-b)(a+b)(a^2-ab+b^2)(a^2+ab+b^2), a^6+b^6=\overline Q_4(a,b)\overline Q_(a,b) = (a^2+b^2)(a^4-a^2b^2+b^4), since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.


Polynomials

For polynomials, factorization is strongly related with the problem of solving
algebraic equation In mathematics, an algebraic equation or polynomial equation is an equation of the form P = 0, where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For example, x^5-3x+1=0 is an algebraic equati ...
s. An algebraic equation has the form :P(x)\ \,\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 plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
of the polynomial) is a value of such that :P(r)=0. If P(x)=Q(x)R(x) 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, the factor theorem connects polynomial factors with polynomial roots. Specifically, if f(x) is a polynomial, then x - a is a factor of f(x) if and only if f (a) = 0 (that is, a is a root of the polynomial). The theorem is a special cas ...
asserts that, if is a root of , then may be factored as :P(x)=(x-r)Q(x), where is the quotient of
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of by the linear (degree one) factor . If the coefficients of are real or
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
numbers, the
fundamental theorem of algebra The fundamental theorem of algebra, also called d'Alembert's theorem or the d'Alembert–Gauss theorem, states that every non-constant polynomial, constant single-variable polynomial with Complex number, complex coefficients has at least one comp ...
asserts that has a real or complex root. Using the factor theorem recursively, it results that :P(x)=a_0(x-r_1)\cdots (x-r_n), 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 object, mathematical objects and are called "equal up to an equivalence relation " * if and are related by , that is, * if holds, that is, * if the equivalence classes of and with respect to are equal. This figure of speech ...
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, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, if a and b are real numbers, then the complex conjugate of a + bi is a - ...
is also a root of . So, the product :(x-r)(x-s) = x^2-(r+s)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 numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor ...
s. In practice, most algebraic equations of interest have
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
or
rational Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...
coefficients, and one may want a factorization with factors of the same kind. The
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 is prime or can be represented uniquely as a product of prime numbers, ...
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(x)=q\,P_1(x)\cdots P_k(x), where is a rational number and P_1(x), \ldots, P_k(x) are non-constant polynomials with integer coefficients that are irreducible and primitive; this means that none of the P_i(x) 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 mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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 and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same doma ...
. 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 of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...
coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which is primitive (that is, the
greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
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 = (-5)\cdot (2x^2 - x - 1) :\fracx^5 + \frac x^2 + 2x + 1 = \frac ( 2x^5 + 21x^2 + 12x + 6) In this factorization, the rational number is called the content, and the primitive polynomial is the primitive part. The computation of this factorization may be done as follows: firstly, reduce all coefficients to a common denominator, for getting the quotient by an integer 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 integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
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 plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
of a
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
:P(x)=a_0x^n+a_1x^+\cdots+a_x+a_n, meaning , then there is a factorization :P(x)=(x-r)Q(x), where :Q(x)=b_0x^+\cdots+b_x+b_, with a_0=b_0. Then
polynomial long division In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, bec ...
or
synthetic division In algebra, synthetic division is a method for manually performing Euclidean division of polynomials, with less writing and fewer calculations than long division. It is mostly taught for division by linear monic polynomials (known as Ruffini ...
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(x) = 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 = (x - 1)(x^2 + x - 2).


Rational roots

For polynomials with rational number coefficients, one may search for roots which are rational numbers. Primitive part-content factorization (see
above Above may refer to: *Above (artist) Tavar Zawacki (b. 1981, California) is a Polish, Portuguese - American abstract artist and internationally recognized visual artist based in Berlin, Germany. From 1996 to 2016, he created work under the ...
) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivial common divisor. If x=\tfrac pq is a rational root of such a polynomial :P(x)=a_0x^n+a_1x^+\cdots+a_x+a_n, the factor theorem shows that one has a factorization :P(x)=(qx-p)Q(x), 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 form In statistics, and particularly in econometrics, the reduced form of a simultaneous equations model, system of equations is the result of solving the system for the endogenous variables. This gives the latter as functions of the exogenous variables, ...
, 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(x)=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 = (2x -3)(x^2 -2x + 2).


Quadratic ac method

The above method may be adapted for
quadratic polynomial In mathematics, a quadratic function of a single variable is a function of the form :f(x)=ax^2+bx+c,\quad a \ne 0, where is its variable, and , , and are coefficients. The expression , especially when treated as an object in itself rather tha ...
s, leading to the ''ac method'' of factorization. Consider the quadratic polynomial :P(x)=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 relate the coefficients of a polynomial to sums and products of its roots. They are named after François Viète (1540-1603), more commonly referred to by the Latinised form of his name, "Franciscus Vieta." Basi ...
, the other root r_2 is :r_2 = -\frac ba - r_1 = -\frac ba-\frac ra =-\fraca = \frac sa, with s=-(b+r). 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(ax^2+bx+c) = (ax-r)(ax-s). 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(x+\tfrac 23)(x+\tfrac 32)= (3x+2)(2x+3).


Using formulas for polynomial roots

Any univariate
quadratic polynomial In mathematics, a quadratic function of a single variable is a function of the form :f(x)=ax^2+bx+c,\quad a \ne 0, where is its variable, and , , and are coefficients. The expression , especially when treated as an object in itself rather tha ...
ax^2+bx+c can be factored using the
quadratic formula In elementary algebra, the quadratic formula is a closed-form expression describing the solutions of a quadratic equation. Other ways of solving quadratic equations, such as completing the square, yield the same solutions. Given a general quadr ...
: : ax^2 + bx + c = a(x - \alpha)(x - \beta) = a\left(x - \frac\right) \left(x - \frac\right), where \alpha and \beta are the two
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...
of the polynomial. If are all real, the factors are real if and only if the
discriminant In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the zero of a function, roots without computing them. More precisely, it is a polynomial function of the coef ...
b^2-4ac is non-negative. Otherwise, the quadratic polynomial cannot be factorized into non-constant real factors. The quadratic formula is valid when the coefficients belong to any field of characteristic different from two, and, in particular, for coefficients in a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
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, a crystal system w ...
and quartic 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 polynomial equations of degree five or higher with arbitrary coefficients. Here, ''general'' means t ...
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 mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field (mathematics), field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems ...
is based on a systematic study of the relations between roots and coefficients, that include
Vieta's formulas In mathematics, Vieta's formulas relate the coefficients of a polynomial to sums and products of its roots. They are named after François Viète (1540-1603), more commonly referred to by the Latinised form of his name, "Franciscus Vieta." Basi ...
. Here, we consider the simpler case where two roots x_1 and x_2 of a polynomial P(x) satisfy the relation :x_2=Q(x_1), where is a polynomial. This implies that x_1 is a common root of P(Q(x)) and P(x). It is therefore a root of the
greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
of these two polynomials. It follows that this greatest common divisor is a non constant factor of P(x). Euclidean algorithm for polynomials allows computing this greatest common factor. For example, if one know or guess that: P(x)=x^3 -5x^2 -16x +80 has two roots that sum to zero, one may apply Euclidean algorithm to P(x) and P(-x). The first division step consists in adding P(x) to P(-x), giving the
remainder In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient ( integer division). In a ...
of :-10(x^2-16). Then, dividing P(x) 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 = (x -5)(x-4)(x+4).


Unique factorization domains

The integers and the polynomials over a field share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element (a
unit Unit may refer to: General measurement * Unit of measurement, a definite magnitude of a physical quantity, defined and adopted by convention or by law **International System of Units (SI), modern form of the metric system **English units, histo ...
, ±1 in the case of integers) and a product of
irreducible element In algebra, an irreducible element of an integral domain is a non-zero element that is not invertible (that is, is not a unit), and is not the product of two non-invertible elements. The irreducible elements are the terminal elements of a factor ...
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, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
s which share this property are called
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
s (UFD).
Greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
s exist in UFDs, but not every integral domain in which greatest common divisors exist (known as a
GCD domain In mathematics, a GCD domain (sometimes called just domain) is an integral domain ''R'' with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated ...
) is a UFD. Every
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain (that is, a non-zero commutative ring without nonzero zero divisors) in which every ideal is principal (that is, is formed by the multiples of a single element). Some author ...
is a 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 Euclidean function which allows a suitable generalization of Euclidean division of integers. Th ...
is an integral domain on which is defined a
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
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 a ...
for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of a field such that there cannot exist any factorization algorithm in the Euclidean domain of the univariate polynomials over .


Ideals

In
algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
, the study of
Diophantine equation ''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: *Diophantine approximation In number theory, the study of Diophantine approximation deals with the approximation of real n ...
s led mathematicians, during 19th century, to introduce generalizations of the
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s called
algebraic integer In algebraic number theory, an algebraic integer is a complex number that is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients ...
s. The first
ring of algebraic integers In algebraic number theory, an algebraic integer is a complex number that is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients a ...
that have been considered were
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf ...
s and
Eisenstein integer In mathematics, the Eisenstein integers (named after Gotthold Eisenstein), occasionally also known as Eulerian integers (after Leonhard Euler), are the complex numbers of the form : z = a + b\omega , where and are integers and : \omega = \frac ...
s, which share with usual integers the property of being
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain (that is, a non-zero commutative ring without nonzero zero divisors) in which every ideal is principal (that is, is formed by the multiples of a single element). Some author ...
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
sqrt In mathematics, a square root of a number is a number such that y^2 = x; in other words, a number whose ''square'' (the result of multiplying the number by itself, or y \cdot y) is . For example, 4 and −4 are square roots of 16 because 4 ...
in which :9=3\cdot 3 = (2+\sqrt)(2-\sqrt), 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, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive number, positive integers , , and satisfy the equation for any integer value of greater than . The cases ...
(probably including Fermat's ''"truly marvelous proof of this, which this margin is too narrow to contain"'') were based on the implicit supposition of unique factorization. This difficulty was resolved by
Dedekind Julius Wilhelm Richard Dedekind (; ; 6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. H ...
, who proved that the rings of algebraic integers have unique factorization of ideals: in these rings, every ideal is a product of
prime ideal In algebra, a prime ideal is a subset of a ring (mathematics), ring that shares many important properties of a prime number in the ring of Integer#Algebraic properties, integers. The prime ideals for the integers are the sets that contain all th ...
s, and this factorization is unique up the order of the factors. The
integral domain In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
s that have this unique factorization property are now called
Dedekind domain In mathematics, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily un ...
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 (: matrices or matrixes) 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 m ...
as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the
LU decomposition In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix multiplication and matrix decomposition). The produ ...
gives a matrix as the product of a lower triangular matrix by an
upper triangular matrix In mathematics, 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 all the entries ''below'' the main diagonal are ...
. As this is not always possible, one generally considers the "LUP decomposition" having a
permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...
as its third factor. See Matrix decomposition for the most common types of matrix factorizations. A
logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in ...
represents a
binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
, and
matrix multiplication In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
corresponds to
composition of relations In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a difunctional relation.


See also

* Euler's factorization method for integers * Fermat's factorization method for integers * Monoid factorisation *
Multiplicative partition In 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. The number ...
* Table of Gaussian integer factorizations


Notes


References

* * * * *


External links

*
Wolfram Alpha WolframAlpha ( ) is an answer engine developed by Wolfram Research. It is offered as an online service that answers factual queries by computing answers from externally sourced data. History Launch preparations for WolframAlpha began on Ma ...
br>can factorize too
{{Authority control Arithmetic Elementary algebra Factorization