factor

Factor a polynomial into irreducible polynomials

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

factor(f, <Adjoin = adjoin>, <MaxDegree = n>)
factor(f, F | Domain = F | Full)

Description

factor(f) computes a factorization f = uf1e1 … frer of the polynomial f, where u is the content of f, f1, …, fr are the distinct primitive irreducible factors of f, and e1, …, er are positive integers.

factor rewrites its argument as a product of as many terms as possible. In a certain sense, it is the complementary function of expand, which rewrites its argument as a sum of as many terms as possible.

If f is a polynomial whose coefficient ring is not Expr, then f is factored over its coefficient ring. See Example 10.

If f is a polynomial with coefficient ring Expr, then f is factored over the smallest ring containing the coefficients. Mathematically, this implied coefficient ring always contains the ring of integers. See Example 4. If the coefficient ring R of f is not Expr, then we say that the implied coefficient ring is R. Elements of the implied coefficient ring are considered to be constants and are not factored any further. In particular, the content u is an element of the implied coefficient ring.

With the option Adjoin, the elements of adjoin are also adjoined to the coefficient ring.

If the second argument F or, alternatively, Domain = Fis given, then f is factored over the real numbers or the complex numbers . Factorization over or is performed using numerical calculations and the results will contain floating-point numbers. See Example 5.

If f is an arithmetical expression but not a number, it is considered as a rational expression. Non-rational subexpressions such as sin(x), exp(1), x^(1/3) etc., but not constant algebraic subexpressions such as I and (sqrt(2)+1)^3, are replaced by auxiliary variables before factoring. Algebraic dependencies of the subexpressions, such as the equation cos(x)2 = 1 - sin(x)2, are not necessarily taken into account. See Example 7.

The resulting expression is then written as a quotient of two polynomial expressions in the original and the auxiliary indeterminates. The numerator and the denominator are converted into polynomials with coefficient ring Expr via poly, and the implied coefficient ring is the smallest ring containing the coefficients of the numerator polynomial and the denominator polynomial. Usually, this is the ring of integers. Then both polynomials are factored over the implied coefficient ring, and the multiplicities ei corresponding to factors of the denominator are negative integers; see Example 3. After the factorization, the auxiliary variables are replaced by the original subexpressions. See Example 6.

If f is an integer, then it is decomposed into a product of primes, and the result is the same as for ifactor. If f is a rational number, then both the numerator and the denominator are decomposed into a product of primes. In this case, the multiplicities ei corresponding to factors of the denominator are negative integers. See Example 2.

If f is a floating point number or a complex number, then factor returns a factorization with the single factor f.

The result of factor is an object of the domain type Factored. Let g:=factor(f) be such an object.

It is represented internally by the list[u, f1, e1, ..., fr, er] of odd length 2 r + 1. Here, f1 through fr are of the same type as the input (either polynomials or expressions); e1 through er are integers; and u is an arithmetical expression.

One may extract the content u and the terms fiei by the ordinary index operator [ ], i.e., g[1] = f1^e1, g[2] = e1^e2, ... if u = 1 and g[1] = u, g[2] = f1^e1, g[3] = e1^e2, ..., respectively, if u ≠ 1.

The call Factored::factors(g) yields the list [f1, f2, ...] of factors, the call Factored::exponents(g) returns the list [e1, e2, ...] of exponents.

The call coerce(g,DOM_LIST) returns the internal representation of a factored object, i.e., the list [u, f1, e1, f2, e2, ...].

Note that the result of factor is printed as an expression, and it is implicitly converted into an expression whenever it is processed further by other MuPAD® functions. As an example, the result of q:=factor(x^2+2*x+1) is printed as (x+1)^2, which is an expression of type "_power".

See Example 1 for illustrations, and the help page of Factored for details.

If f is not a number, then each of the polynomials p1, …, pr is primitive, i.e., the greatest common divisor of its coefficients (see content and gcd) over the implied coefficient ring (see above for a definition) is one.

Currently, factoring polynomials is possible over the following implied coefficient rings: integers, real numbers, complex numbers and rational numbers, finite fields—represented by IntMod(n) or Dom::IntegerMod(n) for a prime number n, or by a Dom::GaloisField—, and rings obtained from these basic rings by taking polynomial rings (see Dom::DistributedPolynomial, Dom::MultivariatePolynomial, Dom::Polynomial, and Dom::UnivariatePolynomial), fields of fractions (see Dom::Fraction), and algebraic extensions (see Dom::AlgebraicExtension).

If the input f is an arithmetical expression that is not a number, all occurring floating-point numbers are replaced by continued fraction approximations. The result is sensitive to the environment variable DIGITS, see numeric::rationalize for details.

Examples

Example 1

To factor the polynomial x3 + x, enter:

g := factor(x^3+x)

Usually, expressions are factored over the ring of integers, and factors with non-integral coefficients, such as x - I in the example above, are not considered.

One can access the internal representation of this factorization with the ordinary index operator:

g[1], g[2]

The internal representation of g, as described above, is given by the following command:

coerce(g, DOM_LIST)

The result of the factorization is an object of domain type Factored:

domtype(g)

Some of the functionality of this domain is described in what follows.

One may extract the factors and exponents of the factorization also in the following way:

Factored::factors(g), Factored::exponents(g)

One can ask for the type of factorization:

Factored::getType(g)

This output means that all fi are irreducible. Other possible types are "squarefree" (see polylib::sqrfree) or "unknown".

One may multiply factored objects, which preserves the factored form:

g2 := factor(x^2 + 2*x + 1)

g * g2

It is important to note that one can apply (almost) any function working with arithmetical expressions to an object of type Factored. However, the result is then usually not of domain type Factored:

expand(g);
domtype(%)

For a detailed description of these objects, please refer to the help page of the domain Factored.

Example 2

factor splits an integer into a product of prime factors:

factor(8)

For rational numbers, both the numerator and the denominator are factored:

factor(10/33)

Note that, in contrast, constant polynomials are not factored:

factor(poly(8, [x]))

Example 3

Factors of the denominator are indicated by negative multiplicities:

factor((z^2 - 1)/z^2)

Factored::factors(%), Factored::exponents(%)

Example 4

If some coefficients are irrational but algebraic, the factorization takes place over the smallest field extension of the rationals that contains all of them. Hence, x^2+1 is considered irreducible while its I-fold is considered reducible:

factor(x^2 + 1), factor(I*x^2 + I)

MuPAD does not automatically factor over the field of algebraic numbers; only the coefficients of the input are adjoined to the rationals:

factor(sqrt(2)*x^4 - sqrt(2)*x^2 - sqrt(2)*2)

factor(I*x^4 - I*x^2 - I*2)

factor(sqrt(2)*I*x^4 - sqrt(2)*I*x^2 - sqrt(2)*I*2)

Example 5

With the option Adjoin, additional elements can be adjoined to the implied coefficient ring:

factor(x^2 + 1, Adjoin = [I])

factor( x^2-2, Adjoin = {sqrt(2)} )

With the option Full, a complete factorization into linear factors can be computed.

factor( x^2-2, Full)

If the argument R_ or C_ is given, factorization is done over the real or complex numbers using numeric calculations:

factor( x^2-2, R_ )

factor(x^2 + 1, C_)

Example 6

Transcendental objects are treated as indeterminates:

delete x:
factor(7*(cos(x)^2 - 1)*sin(1)^3)

Factored::factors(%), Factored::exponents(%)

Example 7

factor regards transcendental subexpressions as algebraically independent of each other. Sometimes, the dependence is recognized:

factor(x + 2*sqrt(x) + 1)

In many cases, however, the algebraic dependence is not recognized:

factor(x^2 + (2^y*3^y + 6^y)* x + (6^y)^2)

Example 8

factor replaces floating-point numbers by continued fraction approximations, factors the resulting polynomial, and finally applies float to the coefficients of the factors:

factor(x^2 + 2.0*x - 8.0)

Example 9

factor with the option Full can use RootOf to symbolically represent the roots of a polynomial:

factor(x^5 + x^2 + 1, Full)

Example 10

Polynomials with a coefficient ring other than Expr are factored over their coefficient ring. We factor the following polynomial modulo 17:

R := Dom::IntegerMod(17): f:= poly(x^3 + x + 1, R):
factor(f)

For every p, the expression IntMod(p) may be used instead of Dom::IntegerMod(p):

R := IntMod(17): f:= poly(x^3 + x + 1, R):
factor(f)

Example 11

More complex domains are allowed as coefficient rings, provided they can be obtained from the rational numbers or from a finite field by iterated construction of algebraic extensions, polynomial rings, and fields of fractions. In the following example, we factor the univariate polynomial u2 - x3 in u over the coefficient field :

Q := Dom::Rational:
Qx := Dom::Fraction(Dom::DistributedPolynomial([x], Q)):
F := Dom::AlgebraicExtension(Qx, poly(z^2 - x, [z])):
f := poly(u^2 - x^3, [u], F)

factor(f)

Parameters

f

A polynomial or an arithmetical expression

F

R_ or C_

Options

MaxDegree

Option, specified as MaxDegree = n

Only algebraic numbers of a maximum degree n will be adjoined to the rational numbers. If not specified, all coefficients up to degree 2 are adjoined. n must be a positive integer.

Adjoin

Option, specified as Adjoin = adjoin

In addition to the coefficients of f, the elements of adjoin are adjoined to the rational numbers. Elements of algebraic degree larger than the value of the option MaxDegree are not adjoined. adjoin must be a set or list.

Domain

Option, specified as Domain = F

Compute a numerical factorization over or , respectively.

Full

Compute the full factorization of f into linear factors. This option has no effect on multivariate polynomials.

Return Values

Object of the domain type Factored.

Overloaded By

f

Algorithms

The factoring algorithms are collected in a separate library domain faclib; it should not be necessary to call these routines directly.

The implemented algorithms include Cantor-Zassenhaus (over finite fields) and Hensel lifting (over the rational numbers and in the multivariate case).

Was this topic helpful?