## Classical division with remainder

We assume that is a commutative ring with identity element. We consider the classical algorithm for univariate polynomial division with remainder stated over instead of a field. However, Algorithm 1 is well defined because we assume that the leading coefficient of the polynomial is a unit.

Algorithm 1

Proposition 1   Let and two univariate polynomials in with respective degrees and such that and the leading coefficient of is a unit. Then there exist unique polynomials and such that and . The polynomials and are called the quotient and the remainder of w.r.t. to . Algorithm 1 compute them in operations in .

Proof. We leave to the reader the proof of the uniqueness of the quotient and the remainder of w.r.t. to . So we focus now on the complexity result Consider an iteration of the for loop where holds at the begining of the loop. Observe that and have the same leading coefficient. Since , computing the reductum of requires operations. Then subtracting the reductum of to that of requires again operations. Hence each iteration of the for loop requires at most operations in , since we need also to count for the computation of . The number of for loops is . Therefore Algorithm 1 requires .

Remark 1   One can derive from Algorithm 1 a bound for the coefficients of and , which is needed for performing a modular version (based for instance on the CRT). Let , and be the max-norm of , and . Let be the absolute value (over ) or the norm (over ) of the leading coefficient of . Then we have

 (1)

Marc Moreno Maza
2008-01-07