# What is the algorithm for long division of polynomials with multiple variables?

I was helping a high-school student last night whose teacher had given as a homework problem the division $$\frac{15x^4-y^2}{x^2+y};$$ I tried a heuristic involving splitting off a difference of squares to end up with $$15x^2-15y+\frac{14y^2}{x^2+y},$$ but I was not satisfied because the remainder has the same degree as the denominator and normally problems like these should end up with a denominator of lower degree.

I next tried variants of synthetic division "with respect to $y$" and "with respect to $x^2$" and got nothing simpler.

I then tried the method outlined in Karl's Calculus Tutor to perform long division, first with the original fraction and then with the remainder term arrived at with the first method that came to my head, and I kept looping; unlike numerical or single-variable long division, multi-variable long division doesn't seem to follow an ordered progression inexorably leading toward a definite remainder of lower degree (in the case of numerical long division, of smaller absolute value) than the denominator, except in simple cases like in the example from Karl's Calculus Tutor.

You can look at this http://en.wikipedia.org/wiki/Multivariate_division_algorithm but keep in mind that it depends on the order you've placed on the monomials. Consider the answer you've obtained. If place the lexicographic order on monomials. Meaning $x^n y^m \geq x^k y^j$ if either $n > k$ or $n = k$ and $m > j$. Then in fact your answer has a proper residue since $y^2 < x^2$.
• Does this also apply to the equivalent division $\frac{15x^2-y^2}{x+y}$ with corresponding expansion $15x-15y+\frac{14y^2}{x+y}$? It does appear to apply by the lexicographic order but it's even more disturbing because the apparent remainder has higher order than the denominator; also I have tried to use a Gröbner basis but the basis turned out to be trivial so it didn't help. – James Edward Lewis II Apr 10 '11 at 20:43
• With the lexicographic order the remainder has a smaller degree since $x > y^2$ by the order. You don't need the basis just use use the multivariate division algorithm. Also I'd advise math.uiuc.edu/Macaulay2 as a way to verify your computations. If you want Eisenbud's book "Commutative Algebra..." has a wonderful part about Groebner basis and its uses. – shamovic Apr 10 '11 at 20:51