# Algebraic Operations on Polynomials

For many kinds of practical calculations, the only operations you will need to perform on polynomials are essentially structural ones.

If you do more advanced algebra with polynomials, however, you will have to use the algebraic operations discussed in this tutorial.

You should realize that most of the operations discussed in this tutorial work only on ordinary polynomials, with integer exponents and rational-number coefficients for each term.

PolynomialQuotient[poly_{1},poly_{2},x] | find the result of dividing the polynomial in x by , dropping any remainder term |

PolynomialRemainder[poly_{1},poly_{2},x] | find the remainder from dividing the polynomial in x by |

PolynomialQuotientRemainder[poly_{1},poly_{2},x] | |

give the quotient and remainder in a list | |

PolynomialMod[poly,m] | reduce the polynomial poly modulo m |

PolynomialGCD[poly_{1},poly_{2}] | find the greatest common divisor of two polynomials |

PolynomialLCM[poly_{1},poly_{2}] | find the least common multiple of two polynomials |

PolynomialExtendedGCD[poly_{1},poly_{2}] | find the extended greatest common divisor of two polynomials |

Resultant[poly_{1},poly_{2},x] | find the resultant of two polynomials |

Subresultants[poly_{1},poly_{2},x] | find the principal subresultant coefficients of two polynomials |

Discriminant[poly,x] | find the discriminant of the polynomial poly |

GroebnerBasis[{poly_{1},poly_{2},...},{x_{1},x_{2},...}] | |

find the Gröbner basis for the polynomials | |

GroebnerBasis[{poly_{1},poly_{2},...},{x_{1},x_{2},...},{y_{1},y_{2},...}] | |

find the Gröbner basis eliminating the | |

PolynomialReduce[poly,{poly_{1},poly_{2},...},{x_{1},x_{2},...}] | |

find a minimal representation of poly in terms of the |

Given two polynomials and , one can always uniquely write , where the degree of is less than the degree of . PolynomialQuotient gives the quotient , and PolynomialRemainder gives the remainder .

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

PolynomialMod is essentially the analog for polynomials of the function Mod for integers. When the modulus m is an integer, PolynomialMod[poly, m] simply reduces each coefficient in poly modulo the integer m. If m is a polynomial, then PolynomialMod[poly, m] effectively tries to get a polynomial with as low a degree as possible by subtracting from poly appropriate multiples of m. The multiplier q can itself be a polynomial, but its degree is always less than the degree of poly. PolynomialMod yields a final polynomial whose degree and leading coefficient are both as small as possible.

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

The main difference between PolynomialMod and PolynomialRemainder is that while the former works simply by multiplying and subtracting polynomials, the latter uses division in getting its results. In addition, PolynomialMod allows reduction by several moduli at the same time. A typical case is reduction modulo both a polynomial and an integer.

In[7]:= |

Out[7]= |

PolynomialGCD[poly_{1}, poly_{2}] finds the highest degree polynomial that divides the exactly. It gives the analog for polynomials of the integer function GCD.

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

The function Resultant[poly_{1}, poly_{2}, x] is used in a number of classical algebraic algorithms. The resultant of two polynomials and , both with leading coefficient one, is given by the product of all the differences between the roots of the polynomials. It turns out that for any pair of polynomials, the resultant is always a polynomial in their coefficients. By looking at when the resultant is zero, you can tell for what values of their parameters two polynomials have a common root. Two polynomials with leading coefficient one have common roots if exactly the first elements in the list Subresultants[poly_{1}, poly_{2}, x] are zero.

In[11]:= |

Out[11]= |

The function Discriminant[poly, x] is the product of the squares of the differences of its roots. It can be used to determine whether the polynomial has any repeated roots. The discriminant is equal to the resultant of the polynomial and its derivative, up to a factor independent of the variable.

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

Gröbner bases appear in many modern algebraic algorithms and applications. The function GroebnerBasis[{poly_{1}, poly_{2}, ...}, {x_{1}, x_{2}, ...}] takes a set of polynomials, and reduces this set to a canonical form from which many properties can conveniently be deduced. An important feature is that the set of polynomials obtained from GroebnerBasis always has exactly the same collection of common roots as the original set.

In[14]:= |

Out[14]= |

In[15]:= |

Out[15]= |

In[16]:= |

Out[16]= |

PolynomialReduce[poly, {p_{1}, p_{2}, ...}, {x_{1}, x_{2}, ...}] yields a list of polynomials with the property that is minimal and is exactly poly.

In[17]:= |

Out[17]= |

Factor[poly] | factor a polynomial |

FactorSquareFree[poly] | write a polynomial as a product of powers of square-free factors |

FactorTerms[poly,x] | factor out terms that do not depend on x |

FactorList[poly], FactorSquareFreeList[poly], FactorTermsList[poly] | |

give results as lists of factors |

Functions for factoring polynomials.

Factor, FactorTerms, and FactorSquareFree perform various degrees of factoring on polynomials. Factor does full factoring over the integers. FactorTerms extracts the "content" of the polynomial. FactorSquareFree pulls out any multiple factors that appear.

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

In[20]:= |

Out[20]= |

In[21]:= |

Out[21]= |

Particularly when you write programs that work with polynomials, you will often find it convenient to pick out pieces of polynomials in a standard form. The function FactorList gives a list of all the factors of a polynomial, together with their exponents. The first element of the list is always the overall numerical factor for the polynomial.

The form that FactorList returns is the analog for polynomials of the form produced by FactorInteger for integers.

In[22]:= |

Out[22]= |

Factor[poly,GaussianIntegers->True] | |

factor a polynomial, allowing coefficients that are Gaussian integers |

Factoring polynomials with complex coefficients.

Factor and related functions usually handle only polynomials with ordinary integer or rational-number coefficients. If you set the option GaussianIntegers->True, however, then Factor will allow polynomials with coefficients that are complex numbers with rational real and imaginary parts. This often allows more extensive factorization to be performed.

In[23]:= |

Out[23]= |

In[24]:= |

Out[24]= |

IrreduciblePolynomialQ[poly] | test whether poly is an irreducible polynomial over the rationals |

IrreduciblePolynomialQ[poly,GaussianIntegers->True] | test whether poly is irreducible over the Gaussian rationals |

IrreduciblePolynomialQ[poly,Extension->Automatic] | test irreducibility over the rationals extended by the algebraic number coefficients of poly |

A polynomial is irreducible over a field if it cannot be represented as a product of two nonconstant polynomials with coefficients in .

In[25]:= |

Out[25]= |

In[26]:= |

Out[26]= |

In[27]:= |

Out[27]= |

In[28]:= |

Out[28]= |

Cyclotomic[n,x] | give the cyclotomic polynomial of order n in x |

Cyclotomic polynomials arise as "elementary polynomials" in various algebraic algorithms. The cyclotomic polynomials are defined by , where runs over all positive integers less than that are relatively prime to .

In[29]:= |

Out[29]= |

In[30]:= |

Out[30]= |

Decompose[poly,x] | decompose poly, if possible, into a composition of a list of simpler polynomials |

Factorization is one important way of breaking down polynomials into simpler parts. Another, quite different, way is *decomposition*. When you factor a polynomial , you write it as a product of polynomials . Decomposing a polynomial consists of writing it as a *composition* of polynomials of the form .

In[31]:= |

Out[31]= |

In[32]:= |

In[33]:= |

Out[33]= |

In[34]:= |

Out[34]= |

Decompose[poly, x] is set up to give a list of polynomials in , which, if composed, reproduce the original polynomial. The original polynomial can contain variables other than , but the sequence of polynomials that Decompose produces are all intended to be considered as functions of .

Unlike factoring, the decomposition of polynomials is not completely unique. For example, the two sets of polynomials and , related by and give the same result on composition, so that . *Mathematica* follows the convention of absorbing any constant terms into the first polynomial in the list produced by Decompose.

InterpolatingPolynomial[{f_{1},f_{2},...},x] | |

give a polynomial in x which is equal to when x is the integer i | |

InterpolatingPolynomial[{{x_{1},f_{1}},{x_{2},f_{2}},...},x] | |

give a polynomial in x which is equal to when x is |

Generating interpolating polynomials.

In[35]:= |

Out[35]= |

In[36]:= |

Out[36]= |