# 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.

See Chapter 2, Section 3 (p. 61) in the book Ideals, varieties, and algorithms by Cox, Little & O'Shea. (Google books link.)

• I wish I were able to mark both answers as my accepted answer, but yours is even more generalized. Apr 10, 2011 at 20:45
• Thanks for posting this reference, I'll make sure to read it. It seems to me that all the examples that illustrate how division isn't automatically well-defined for multivariate polynomials involve higher-order monomials. If we restrict to polynomials where each monomial is multilinear, is there still a need to do all this Grobner basis business, ie. defining an ordering etc?
– gen
Aug 28, 2021 at 17:08
• @gen: By multilinear monomial, do you mean $x_1^{k_1} \cdots x_n^{k_n}$ where each $k_i$ is either zero or one? Aug 30, 2021 at 5:27
• @HansLundmark yes, that’s what i mean.
– gen
Aug 30, 2021 at 20:01
• @gen: OK, but I'm still not quite sure I understand what you mean by “isn't automatically well-defined”. Clearly the quotients will depend on the order of the polynomials you divide by, and on the chosen monomial order. Are you asking about the remainder being uniquely determined? Sep 1, 2021 at 12:07

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. Apr 10, 2011 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. Apr 10, 2011 at 20:51