Exercise 2.95: Define P
1, P
2, and
P
3 to be the polynomials
P
1
:
x
2
−
2
x
+
1
,
P
2
:
11
x
2
+
7
,
P
3
:
13
x
+
5.
Now define Q
1 to be the product of P
1 and P
2, and Q
2 to be
the product of P
1 and P
3, and use greatest-common-divisor
(Exercise 2.94) to compute the GCD of Q
1 and Q
2.
Note that the answer is not the same as P
1. This example introduces
noninteger operations into the computation, causing difficulties with the
GCD algorithm. To understand what is happening, try tracing
gcd-terms while computing the GCD or try performing the
division by hand.
We can solve the problem exhibited in Exercise 2.95 if we use the
following modification of the GCD algorithm (which really works only
in the case of polynomials with integer coefficients). Before performing any
polynomial division in the GCD computation, we multiply the dividend
by an integer constant factor, chosen to guarantee that no fractions will arise
during the division process. Our answer will thus differ from the actual
GCD by an integer constant factor, but this does not matter in the
case of reducing rational functions to lowest terms; the GCD will be
used to divide both the numerator and denominator, so the integer constant
factor will cancel out.
More precisely, if P and Q are polynomials, let O
1 be the order of
P (i.e., the order of the largest term of P) and let O
2 be the
order of Q. Let c be the leading coefficient of Q. Then it can be
shown that, if we multiply P by the
integerizing factor
c
1
+
O
1
−
O
2, the resulting polynomial can be divided by Q by
using the div-terms algorithm without introducing any fractions. The
operation of multiplying the dividend by this constant and then dividing is
sometimes called the
pseudodivision of P by Q. The remainder
of the division is called the
pseudoremainder.
练习 2.95：将 P₁、P₂ 和 P₃ 定义为以下多项式：
P₁: x² − 2x + 1，P₂: 11x² + 7，P₃: 13x + 5。
现在将 P₁ 与 P₂ 的积定义为 Q₁，P₁ 与 P₃ 的积定义为 Q₂，并用 greatest-common-divisor（练习 2.94）计算 Q₁ 和 Q₂ 的 GCD。注意，所得答案与 P₁ 并不相同。这个例子在计算中引入了非整数操作，导致 GCD 算法出现困难。为了理解发生了什么，可以在计算 GCD 时追踪 gcd-terms 的调用，或手动执行除法。
如果我们采用以下对 GCD 算法的修改（该修改实际上仅适用于整数系数的多项式），就可以解决练习 2.95 所展示的问题。在 GCD 计算中进行任何多项式除法之前，将被除式乘以一个整数常数因子，该因子的选取应保证除法过程中不会出现分数。这样，我们的答案与真正的 GCD 相差一个整数常数因子，但在将有理函数化为最简形式的情况下，这无关紧要：GCD 将同时除分子和分母，整数常数因子会相互抵消。
更精确地说，设 P 和 Q 是多项式，O₁ 为 P 的阶数（即 P 的最高次项的阶数），O₂ 为 Q 的阶数，c 为 Q 的首项系数。那么可以证明，若将 P 乘以整数化因子 c^(1 + O₁ − O₂)，所得多项式即可用 div-terms 算法被 Q 整除而不引入任何分数。将被除式乘以这个常数再进行除法的操作有时称为 P 被 Q 的伪除法 (pseudodivision)，所得余式称为伪余式 (pseudoremainder)。