Pseudo-division

also: pseudo remainder, prem

Polynomial division made to stay inside a ring that is not a field, by multiplying the dividend by a power of the divisor's leading coefficient first. Nothing ever becomes a fraction, and the price is that coefficients square at every step, which is the problem the subresultant correction exists to solve.

Over a field, dividing $u$ by $v$ is unproblematic. Over $Z$ , or over a ring of polynomials in the other variables, it is not: dividing $x^{2}$ by $3 x + 1$ leaves a third. Pseudo-division buys its way out by scaling the dividend first.

lc (v)^{d e g u - d e g v + 1} \cdot u = q v + r, de g r < de g v

Every coefficient produced stays in the ring, and the identity is exact rather than approximate. The price arrives when it is iterated: each remainder is multiplied by a power of the previous leading coefficient, so coefficients square at every step.

Two coprime polynomials of degree 8 and 6 with coefficients under 21. Verbatim.

  prem 1: degree  6, max coefficient 21
  prem 2: degree  4, max coefficient 15
  prem 3: degree  2, max coefficient 59535
  prem 4: degree  1, max coefficient 1654608338437500
  prem 5: degree  0, max coefficient 12593338795500743100931141992187500

Two-digit inputs, a thirty-five-digit intermediate, and an answer of $1$ . The growth is real arithmetic on real bignums, and it is the entire reason the subresultant correction exists.