## Statement

Let and in be two polynomials with respective degrees . We assume that the leading coefficient of divides the leading coefficient of . We want to decide whether divides exactly, that is, whether there exists a polynomial such that holds. Moreover, if divides exactly, we want to compute the quotient .

Another obvious necessary condition (for to divide exactly) is that the trailing coefficient of (that is the coefficient of of its non-zero term with smallest degree) divides that of . So, we assume that this condition holds too.

If and are random enough the probability for to divide exactly is clearly low. So we aim at designing a modular method that will take advantage of this remark.

Marc Moreno Maza
2008-03-18