# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Compute the pseudoquotient and pseudoremainder with respect to a given variable for a pair of polynomials

Contributed by:
Daniel Lichtblau

ResourceFunction["PseudoQuotientRemainder"][ performs pseudodivision of |

ResourceFunction["PseudoQuotientRemainder"] performs the operation of pseudodivision, which is a form of polynomial division that uses cross-multiplication by leading coefficients to avoid actual division in the coefficient arithmetic.

The input polynomials need not be univariate and in common usage are multivariate. Coefficients of the polynomials in the main variable are themselves polynomials in the remaining variables. ResourceFunction["PseudoQuotientRemainder"] avoids dividing by coefficient polynomials.

Pseudodivision is typically used as a step in forming what are called triangular sets for a system of *n* multivariate polynomials in *n* variables.

A pseudodivision of polynomials *p* and *q* returns a triple {*pre*,*quot*,*rem*} satisfying the relation *pre*·*p*=*quot*·*q*+*rem*.

The prefactor returned by ResourceFunction["PseudoQuotientRemainder"] is a power of the leading coefficient of the divisor polynomial, where all coefficients are taken with respect to the specified variable. The power is at most one more than the difference in degrees of the input polynomials with respect to that variable.

With the option Modulus→*n*, the pseudodivision is performed modulo *n* for computing over a prime field.

Create dividend and divisor polynomials and pseudodivide with respect to the variable *x*_{2}:

In[1]:= |

Out[1]= |

Check the result:

In[2]:= |

Out[2]= |

The input polynomials can be univariate:

In[3]:= |

Out[3]= |

Check the result:

In[4]:= |

Out[4]= |

The coefficients in the resulting pseudoquotient and pseudoremainder are grouped with respect to powers of the specified variable:

In[5]:= |

Out[5]= |

Perform pseudodivision modulo 13:

In[6]:= |

Out[6]= |

Take the pseudoquotient and pseudoremainder of a pair of univariate polynomials:

In[7]:= |

Out[7]= |

Iterate, using *q* and *rem*:

In[8]:= |

Out[8]= |

The pseudoremainder is now an integer multiple of the greatest common divisor of *p* and *q*:

In[9]:= |

Out[9]= |

Iterate again and the pseudoremainder will be zero:

In[10]:= |

Out[10]= |

Expand the input polynomials:

In[11]:= |

Out[11]= |

The collection of inputs and pseudoremainders is in fact the polynomial remainder sequence, which can be also computed using SubresultantPolynomialRemainders:

In[12]:= |

Out[12]= |

A substantially similar result can be computed with SubresultantPolynomials:

In[13]:= |

Out[13]= |

Compute the pseudodivision of a pair of parametrized polynomials in *x*:

In[14]:= |

Out[14]= |

PolynomialReduce gives a similar result, along with a common denominator:

In[15]:= |

Out[15]= |

- 1.0.0 – 17 May 2021

This work is licensed under a Creative Commons Attribution 4.0 International License