
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
can be trivially written as
whenever
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 ...
:
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,
:
having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression
:
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,
can be factored into two
irreducible factors and
.
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
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 ''
'', 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,
since 2 is the greatest common divisor of 6, 8, and 10, and
divides all terms.
Grouping
Grouping terms may allow using other methods for getting a factorization.
For example, to factor
one may remark that the first two terms have a common factor , and the last two terms have the common factor . Thus
Then a simple inspection shows the common factor , leading to the factorization
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
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 ...
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
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
* ...
:
Subtracting and adding
also yields the factorization:
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 ...
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,
since
since
since
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 ...
::
:For example,
:::
*;Sum/difference of two cubes
::
::
:*;
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
:::
:::
*;Difference of two fourth powers
::
*;Sum/difference of two th powers
:In the following identities, the factors may often be further factorized:
:*;Difference, even exponent
::
:*;Difference, even or odd exponent
::
::This is an example showing that the factors may be much larger than the sum that is factorized.
:*;Sum, odd exponent
::
::(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
*;Trinomials and cubic formulas
:::
:*;
Argand identity
:::
:::
*;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:
::
::
::
::
:More generally, the coefficients of the expanded forms of
and
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
They are thus the numbers
for
It follows that for any two expressions and , one has:
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
is
and
one has the following real factorizations (one passes from one to the other by changing into or , and applying the usual
trigonometric formulas:
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,
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
its ''homogenization'' is the
bivariate polynomial Then, one has
where the products are taken over all divisors of , or all divisors of that do not divide , and
is the th cyclotomic polynomial.
For example,
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
:
where is a polynomial in with
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
:
If
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
:
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
:
where
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
:
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
:
where is a rational number and
are non-constant polynomials with integer coefficients that are
irreducible and
primitive; this means that none of the
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:
:
:
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
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 ...
:
meaning , then there is a factorization
:
where
:
with
. 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:
:
This may be useful when one knows or can guess a root of the polynomial.
For example, for
one may easily see that the sum of its coefficients is 0, so is a root. As , and
one has
:
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
is a rational root of such a polynomial
:
the factor theorem shows that one has a factorization
:
where both factors have integer coefficients (the fact that has integer coefficients results from the above formula for the quotient of by
).
Comparing the coefficients of degree and the constant coefficients in the above equality shows that, if
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
and is a divisor of
Therefore, there is a finite number of possibilities for and , which can be systematically examined.
For example, if the polynomial
:
has a rational root
with , then must divide 6; that is
and must divide 2, that is
Moreover, if , all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have
:
A direct computation shows that only
is a root, so there can be no other rational root. Applying the factor theorem leads finally to the factorization
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
:
with integer coefficients. If it has a rational root, its denominator must divide evenly and it may be written as a possibly
reducible fraction 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
is
:
with
Thus the second root is also rational, and Vieta's second formula
gives
:
that is
:
Checking all pairs of integers whose product is gives the rational roots, if any.
In summary, if
has rational roots there are integers and such
and
(a finite number of cases to test), and the roots are
and
In other words, one has the factorization
:
For example, let consider the quadratic polynomial
:
Inspection of the factors of leads to , giving the two roots
:
and the factorization
:
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 ...
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 ...
:
:
where
and
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 ...
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
and
of a polynomial
satisfy the relation
:
where is a polynomial.
This implies that
is a common root of
and
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
Euclidean algorithm for polynomials allows computing this greatest common factor.
For example,
if one know or guess that:
has two roots that sum to zero, one may apply Euclidean algorithm to
and
The first division step consists in adding
to
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
:
Then, dividing
by
gives zero as a new remainder, and as a quotient, leading to the complete factorization
:
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
in which
:
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