Graphics Reference
In-Depth Information
then
()
=
2
()
=
()
=
2
lt f
7
X Y
,
lc f
7
,
and
lpp f
X Y
.
In the future, whenever we talk about leading terms, etc., we shall always assume
a monomial order has been chosen even if we do not say so explicitly.
10.10.5. Theorem.
(The Division Algorithm for k[X
1
,X
2
,...,X
n
]) Fix a monomial
order < on k[X
1
,X
2
,...,X
n
] and let P = {p
1
,p
2
,...,p
m
} be a fixed set of m nonzero
polynomials in k[X
1
,X
2
,...,X
n
]. Then every f Πk[X
1
,X
2
,...,X
n
] can be expressed
as
fap ap
=
+
2 2
...
+
+
ap r
+
,
11
mm
where a
i
, r Πk[X
1
,X
2
,...,X
n
] , and either r is zero or none of the monomials appear-
ing in r is divisible by any of the lt(p
i
). The polynomial r will be called a
remainder
of
f by division with respect the sequence of polynomials P. Furthermore,
()
=
{
()
()
( )
( )
( )
( ) ()
}
lpp f
max
lpp a
lpp p
,
lpp a
lpp p
,...,
lpp a
lpp p
,
lp r
.
1
1
2
2
m
m
Proof.
Algorithm 10.10.2 is an algorithm that finds the a
i
and r. Therefore, the proof
of the division theorem boils down to showing that that algorithm does what it claims.
The reader should compare this algorithm with Algorithm 10.10.1 for one variable.
Two key observations for a proof of Algorithm 10.10.2 are:
(1) f = a
1
p
1
+ a
2
p
2
+ ···+ a
m
p
m
+ g + r at each stage.
(2) The leading term of g in (1) decreases with respect to the ordering so that the
algorithm terminates.
See [CoLO97] or [AdaL94].
See Exercise 10.10.4 for a simple variant of a multivariable division algorithm.
Definition.
Let f and g be two polynomials. We say that f is
simpler
than g if lt(f)
< lt(g).
For example, if
2
3
3
3
,
f
=
XY
+
X
and
g
=
X Y
+
Y
then f is simpler than g. Algorithm 10.10.2 shows how to simplify polynomials with
respect to any set of polynomials. We introduce some other common terminology.
Definition.
Fix a monomial order. Let P be a set of polynomials and f an arbitrary
polynomial. Assume that some monomial term u of f is divisible by the leading term
of a polynomial p in P, that is,
