## Statement

Let be a commutative ring. Let be a multiplication time. Hence, for any two polynomials of degree less than one can compute the product in at most operations in . Moreover, for all we have .

Let be two integers. Let be of degree and let be monic polynomials such that the sum of their degrees is .

The goal of this exercise is to show that all remainders can be computed in operations in .

The following result (proved in class) will be essential: division-with-remainder of a polynomial of degree by a monic polynomial of degree (where are non-negative integers) can be done in at most ring operations in where we have

Marc Moreno Maza
2008-03-18