In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, 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.
In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical p ...
as a product of several ''factors'', usually smaller or simpler objects of the same kind. For example, is a factorization of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, and is a factorization of the
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
.
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 fo ...
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 (e.g. ). The set of all ra ...
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
Greek mathematics refers to mathematics texts and ideas stemming from the Archaic through the Hellenistic and Roman periods, mostly extant from the 7th century BC to the 4th century AD, around the shores of the Eastern Mediterranean. Greek mathem ...
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 can be represented uniquely as a product of prime numbers, up to the ord ...
, 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 objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' with respect to ''R'' ...
the order of the factors. Although
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are s ...
is a sort of inverse to multiplication, it is much more difficult
algorithmically, a fact which is exploited in the
RSA cryptosystem
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publi ...
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 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 dom ...
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 focusing ...
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 an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
with
complex coefficients admits a unique (up to ordering) factorization into
linear polynomials: this is a version of the
fundamental theorem of algebra
The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
. In this case, the factorization can be done with
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
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 mathematical expressions ...
. There are efficient computer
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 do ...
).
A
commutative ring
In mathematics, a commutative ring is a 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 properties that are not ...
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 systems, such as certain
rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of
Dedekind domains:
ideals factor uniquely into
prime ideal
In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
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 that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
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; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
.
Matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
possess many kinds of
matrix factorizations. For example, every matrix has a unique
LUP factorization as a product of a
lower 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 a ...
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 and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, whe ...
; 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 operations performed on the corresponding matrix of coefficients. This method can also be used ...
.
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 can be represented uniquely as a product of prime numbers, up to the ord ...
, every
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
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 rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for finding a
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
of or deciding that is prime. When such a divisor is found, the repeated application of this algorithm to the factors and gives eventually the complete factorization of .
For finding a divisor of , if any, it suffices to test all values of such that and . In fact, if is a divisor of such that , then is a divisor of such that .
If one tests the values of in increasing order, the first divisor that is found is necessarily a prime number, and the ''cofactor'' cannot have any divisor smaller than . For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of that is not smaller than and not greater than .
There is no need to test all values of for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the
sieve of Eratosthenes
In mathematics, 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 (i.e., not prime) the multiples of each prime, starting with the first prime n ...
. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3.
This method works well for factoring small integers, but is inefficient for larger integers. For example,
Pierre de Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
was unable to discover that the 6th
Fermat number
:
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) is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent numbers in a positional numeral system. The name "digit" comes from the fact that the ten digits ( Lati ...
s.
There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the
RSA cryptosystem
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publi ...
, which is widely used for secure
internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, p ...
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 one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
. 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 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 example, in F ...
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 focusing ...
''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 Below ...
.
Solving
algebraic equations 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 dom ...
. In fact, the
fundamental theorem of algebra
The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
can be stated as follows: every
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
in of degree with
complex 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 most cases, the best that can be done is computing
approximate values of the roots with a
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
.
History of factorization of expressions
The systematic use of algebraic manipulations for simplifying expressions (more specifically
equation
In mathematics, an equation is a 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 example, in F ...
s)) may be dated to 9th century, with
al-Khwarizmi
Muḥammad ibn Mūsā al-Khwārizmī ( ar, محمد بن موسى الخوارزمي, Muḥammad ibn Musā al-Khwārazmi; ), or al-Khwarizmi, was a Persian polymath from Khwarazm, who produced vastly influential works in mathematics, astronom ...
's book ''
'', which is titled with two such types of manipulation.
However, even for solving
quadratic equation
In algebra, a quadratic equation () is any equation that can be rearranged in standard form as
ax^2 + bx + c = 0\,,
where represents an unknown value, and , , and represent known numbers, where . (If and then the equation is linear, not qu ...
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 power product, is a product of powers of variables with nonnegative integer expon ...
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
trinomials. 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 an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
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 power product, is a product of powers of variables with nonnegative integer expon ...
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 generalizes 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 arithmetic, ...
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) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
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 method for getting the
quadratic formula
In elementary algebra, the quadratic formula is a formula that provides the solution(s) to a quadratic equation. There are other ways of solving a quadratic equation instead of using the quadratic formula, such as factoring (direct factoring, ...
.
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
:
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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
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 that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, the product of two non-squares is a square; this implies that the
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
which is
irreducible over the integers, is reducible
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is ...
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
::
:For example,
::
*;Sum/difference of two cubes
::
::
*;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 (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
:::
*;Binomial expansions
:The
binomial theorem 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 a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although o ...
.
Roots of unity
The th
roots of unity
In mathematics, a root of unity, occasionally called a de Moivre number, 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 ...
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 fo ...
s each of which is a
root
In vascular plants, the roots are the 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 below the su ...
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, then) the complex conjugate of a + bi is equal to 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
cosines that appear in these factorizations are
algebraic number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of th ...
s, and may be expressed in terms of
radicals
Radical may refer to:
Politics and ideology Politics
*Radical politics, the political intent of fundamental societal change
*Radicalism (historical), the Radical Movement that began in late 18th century Britain and spread to continental Europe and ...
(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 po ...
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 primitiv ...
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 quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial of degree 5, in two variables; ...
: 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 equations. 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 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 below the su ...
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 asserts that, if is a root of , then may be factored as
:
where is the quotient of
Euclidean division of by the linear (degree one) factor .
If the coefficients of are
real or
complex numbers, the
fundamental theorem of algebra
The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
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 objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' with respect to ''R'' ...
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, then) the complex conjugate of a + bi is equal to 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 mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s.
In practice, most algebraic equations of interest have
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
or
rational
Rationality is the quality of being guided by or based on reasons. 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 abi ...
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 can be represented uniquely as a product of prime numbers, up to the ord ...
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 rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 mathematical expressions ...
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 do ...
. 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 reasons. 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 abi ...
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) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
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
Content or contents may refer to:
Media
* Content (media), information or experience provided to audience or end-users by publishers or media producers
** Content industry, an umbrella term that encompasses companies owning and providing mas ...
, and the primitive polynomial is the
primitive part
In algebra, the content of a polynomial with integer coefficients (or, more generally, with coefficients in a unique factorization domain) is the greatest common divisor of its coefficients. The primitive part of such a polynomial is the quotient ...
. 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 mathematics, 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 equivale ...
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 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 below the su ...
of a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
:
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 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) 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, 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 polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomial ...
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 (more commonly referred to by the Latinised form of his name, "Franciscus Vieta").
Basic formula ...
, 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 polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomial ...
can be factored using the
quadratic formula
In elementary algebra, the quadratic formula is a formula that provides the solution(s) to a quadratic equation. There are other ways of solving a quadratic equation instead of using the quadratic formula, such as factoring (direct factoring, ...
:
:
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 focusing ...
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 roots without computing them. More precisely, it is a polynomial function of the coefficients of the orig ...
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 that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with an odd number of elements.
There are also formulas for roots of
cubic and
quartic polynomials, which are, in general, too complicated for practical use. The
Abel–Ruffini theorem 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 theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
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 (more commonly referred to by the Latinised form of his name, "Franciscus Vieta").
Basic formula ...
.
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) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
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 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:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
, ±1 in the case of integers) and a product of
irreducible elements (
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, specifically abstract algebra, 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 s ...
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) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
s exist in UFDs, and conversely, every integral domain in which greatest common divisors exist is an UFD. Every
principal ideal domain
In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principa ...
is an UFD.
A
Euclidean domain
In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers ...
is an integral domain on which is defined a
Euclidean division similar to that of integers. Every Euclidean domain is a principal ideal domain, and thus a UFD.
In a Euclidean domain, Euclidean division allows defining a
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an e ...
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 o ...
, the study of
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a ...
s led mathematicians, during 19th century, to introduce generalizations of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s called
algebraic integers. The first
ring of algebraic integers
In algebraic number theory, an algebraic integer is a complex number which 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 coefficient ...
that have been considered were
Gaussian integers 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 = \f ...
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 in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principa ...
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 (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, 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 that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s, and this factorization is unique up the order of the factors. The
integral domain
In mathematics, specifically abstract algebra, 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 s ...
s that have this unique factorization property are now called
Dedekind domains. 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 most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** '' The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
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 decomposition). The product sometimes includes a p ...
gives a matrix as the product of a
lower 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 a ...
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 and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, whe ...
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 (mathematics), matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
...
represents a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
, and
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
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
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
relation.
See also
*
Euler's factorization method for integers
*
Fermat's factorization method for integers
*
Monoid factorisation
*
Multiplicative partition
*
Table of Gaussian integer factorizations
Notes
References
*
*
*
*
*
External links
*
Wolfram Alpha
WolframAlpha ( ) is an answer engine developed by Wolfram Research. It answers factual queries by computing answers from externally sourced data.
WolframAlpha was released on May 18, 2009 and is based on Wolfram's earlier product Wolfram Mat ...
br>
can factorize too
{{Authority control
Arithmetic
Elementary algebra
Factorization