## `factor` -- factor a polynomial into irreducible polynomials

#### Introduction

`factor(`f`)` computes a factorization f = u * f1^e1 * ... * fr^er 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.

#### Call(s)

`factor(f)`

#### Parameters

`f` | - | a polynomial or an arithmetical expression

#### Returns

an object of the domain type `Factored`.

### Overloadable:

`f`

#### Further Documentation

Chapter ``Manipulating Expressions'' of the Tutorial.

#### Related Functions

`collect`, `content`, `denom`, `div`, `divide`, `expand`, `Factored`, `gcd`, `icontent`, `ifactor`, `igcd`, `ilcm`, `indets`, `irreducible`, `isprime`, `lcm`, `normal`, `numer`, `partfrac`, `polylib::decompose`, `polylib::divisors`, `polylib::primpart`, `polylib::sqrfree`, `rationalize`, `simplify`

#### Details

- `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 8.

  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 Z_ 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.

- If `f` is an arithmetical expression that is 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 6.

  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 5.

- 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 2r+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, the factors fi, as well as the exponents ei by the ordinary index operator `[ ]`, i.e., `g[1] = u, g[2] = f1, g[3] = e1, ...`.

  For example, to extract all irreducible factors of f, enter `g[2*i] $ i = 1..nops(g) div 2`. The same can be achieved with the call `Factored::factors(g)`, and the call `Factored::exponents(g)` returns a list of the exponents ei for 1 <= i <= r.

  The call `coerce(g,DOM_LIST)` returns the internal representation of a factored object, i.e., the list as described above.

  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 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`). In particular, factoring over the real and over complex numbers is not possible.

- 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.

#### Example 1

To factor the polynomial x^3 + x, enter:

    >> g := factor(x^3+x)

                                        2
                                    x (x  + 1)

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];                              // the content
       g[2*i]     $ i = 1..nops(g) div 2; // the factors
       g[2*i + 1] $ i = 1..nops(g) div 2; // the exponents

                                         1

                                         2
                                     x, x  + 1

                                       1, 1

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

    >> coerce(g, DOM_LIST)

                                          2
                               [1, x, 1, x  + 1, 1]

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

    >> domtype(g)

                                     Factored

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)

                                     2
                                [x, x  + 1], [1, 1]

One can ask for the type of factorization:

    >> Factored::getType(g)

                                   "irreducible"

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)

                                            2
                                     (x + 1)

    >> g * g2

                                    2             2
                                x (x  + 1) (x + 1)

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(%)

                                           3
                                      x + x

                                     DOM_EXPR

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)

                                         3
                                        2

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

    >> factor(10/33)

                                       2 5
                                       ----
                                       3 11

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

    >> factor(poly(8, [x]))

                                         8

#### Example 3

Factors of the denominator are indicated by negative multiplicities:

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

                                  (z + 1) (z - 1)
                                  ---------------
                                         2
                                        z

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

                           [z, z + 1, z - 1], [-2, 1, 1]

#### 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)

                              2
                             x  + 1, I (x - I) (x + I)

MuPAD cannot 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)

                         1/2       1/2        1/2    2
                        2    (x + 2   ) (x - 2   ) (x  + 1)

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

                                                2
                            I (x - I) (x + I) (x  - 2)

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

                      1/2                1/2                1/2
                  (I 2   ) (x + I) (x + 2   ) (x - I) (x - 2   )

#### Example 5

Transcendental objects are treated as indeterminates:

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

                                                          3
                        7 (exp(x) + 1) (exp(x) - 1) sin(1)

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

                    [exp(x) + 1, exp(x) - 1, sin(1)], [1, 1, 3]

#### Example 6

`factor` regards transcendental subexpressions as algebraically independent of each other. Hence the binomial formula is not applied in the following example:

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

                                         1/2
                                  x + 2 x    + 1

#### Example 7

`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)

                                (x + 4.0) (x - 2.0)

#### Example 8

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)

          poly(x + 6, [x], Dom::IntegerMod(17))

                   2
             poly(x  + 11 x + 3, [x], Dom::IntegerMod(17))

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)

                                             2
          poly(x + 6, [x], IntMod(17)) poly(x  - 6 x + 3, [x], IntMod(17)

             )

#### Example 9

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 u^2-x^3 in u over the coefficient field F = Q(x, sqrt(x)):

    >> 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)

                2    3
          poly(u  - x , [u], Dom::AlgebraicExtension(

             Dom::Fraction(Dom::DistributedPolynomial([x],

                                               2
             Dom::Rational, LexOrder)), - x + z  = 0, z))

    >> factor(f)

          poly(u - x z, [u], Dom::AlgebraicExtension(

             Dom::Fraction(Dom::DistributedPolynomial([x],

                                               2
             Dom::Rational, LexOrder)), - x + z  = 0, z)) poly(u + x z,

             [u], Dom::AlgebraicExtension(Dom::Fraction(

             Dom::DistributedPolynomial([x], Dom::Rational, LexOrder)),

                    2
             - x + z  = 0, z))

#### Background

- 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).

#### Changes

- The return value of `factor` is an object of the domain `Factored`.
- Integers and rational numbers as input are split into a product of prime factors.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000