Recall (that's the `generalized recall', which includes the case where you've never seen it before) the algorithm for integration of rational functions by partial fractions (not to be confused with integration by parts).
We want to integrate where and are polynomials with (say) complex coefficients. Without loss of generality, take monic and assume that the GCD of p and q is . Then by the division algorithm,
where the degree of the remainder is strictly less than the degree of . Let . Using 1 we then have
where is the easily computed integral of the polynomial .
We have thus reduced the problem to one where the rational
function is a `proper fraction'. This idea, of reducing the problem
to simpler ones, underlies all the later algorithms. For now, we
start with the