We now discuss multivariate division and remainders. For a more complete discussion see Cox, Little, and O'Shea. We consider only the case when we are dividing by an ideal for which we have a Gröbner basis (otherwise the remainder is not unique).

** Theorem 3:
Division Algorithm in **. (Cox, Little, O'Shea
p. 63).
Fix a monomial order **>** on , and let
be an ordered **s**-tuple of polynomials in **K**. Then every **f** in
**K** can be written as

where , and either **r = 0** or **r** is a **k**-linear combination of
monomials, none of which is divisible by any of LT, , LT.
We will call **r** a ** remainder** of **f** on division by **F**.
Furthermore, if , then we have

For the algorithm which constructs the and **r**,
and proof of its correctness,
see Cox, Little, and O'Shea.
Note that unless **F** is a Gröbner basis, the remainder **r**
and quotients will * not be unique*.
If, on the other hand, **F** is a Gröbner basis,
then the remainder (but not the quotients) will be unique,
and not depend on the
order of polynomials in the basis.
(This is proposition 1 in Cox, Little, O'Shea,
p. 81.)

** Remark**. The fact that if **r** is not zero then it
is a **k**-linear combination
of `small' monomials is crucial to the linear algebraic aspect of Gröbner bases.
We give
an example here.

** Example** Suppose and
. This is not a Gröbner basis, but we can find
using Maple that is a (grevlex or `tdeg') Gröbner basis for
**F**, where , ,
and .
Using Maple again, with the `normalf`

routine, we find that the remainder of dividing
(say) by this ideal is

normalf(2*x1**4*x2 - x2**2 + x1**3 + x1 + 1, GB, [x1,x2], tdeg);which gives . One important point is that none of the terms in this remainder are divisible by the leading terms of the Gröbner basis (namely , , or ). Another is that the algorithm produces a unique remainder, no matter what ordering is chosen for the basis.

Finally, notice that using this remainder we can define
an equivalence class in **K**,
namely if the remainder on dividing
**f** by **G** is the same as the remainder
on dividing **g** by **G**.
This gives us the quotient ring (see Cox, Little, and O'Shea
for the details verifying that this all makes sense).
We observe, then, that the set of
monomials which are not divisible by the
leading terms of the Gröbner basis form a basis
for this quotient ring. This is what we explore, in section (6.4).
But first, we take advantage of all this notation to give a real definition
of a Gröbner basis, and describe Buchberger's algorithm for computing one.

Tue Mar 12 21:09:19 EST 1996