最大公因式和辗转相除法

节 1.3 最大公因式和辗转相除法

和整数的最大公因数类似，在一元多项式的研究中，多项式的最大公因式具有重要地位，其研究方法和结论也是类似的。

子节 1.3.1 最大公因式的一般理论

定义 1.3.1.

设

f (x), g (x) \in F [x]

。若

d (x) \in F [x]

使得

🔗

$d (x) | f (x)$ 且 $d (x) | g (x)$ ；
若 $h (x) | f (x)$ 且 $h (x) | g (x)$ ，则 $h (x) | d (x)$ ；

则称

d (x)

是

f (x)

与

g (x)

的最大公因式。

🔗

定义中的项 1保证

d (x)

是

f (x)

和

g (x)

的公因式，项 2保证

d (x)

的次数是所有公因式次数的最大值。

🔗

根据项 2，若

d_{1} (x)

和

d_{2} (x)

都是

f (x)

和

g (x)

的最大公因式，则

d_{1} (x)

和

d_{2} (x)

相互整除，即

d_{1} (x)

和

d_{2} (x)

相伴。另一方面，若

d_{1} (x)

和

d_{2} (x)

相伴，则此时

d_{1} (x)

和

d_{2} (x)

只相差一个非0常数的数乘，

d_{1} (x)

和

d_{2} (x)

一定同时满足或同时不满足最大公因式的两个条件。总之，

f (x)

和

g (x)

的所有最大公因式构成一个相伴多项式类。为了简单，当这个相伴类不是只有0多项式时，我们选择其中唯一的一个首1多项式做为最大公因式的代表，并将其记为

🔗

(f (x), g (x)) .

特别地，约定

(0, 0) = 0

。

🔗

有了最大公因式的定义后，我们需要考虑的首要问题是最大公因式是否存在。其次，如果最大公因式存在，应该如何求出给定的两个多项式的最大公因式？直觉告诉我们，当

f (x)

和

g (x)

的次数越小，其最大公因式应该越好求。下面的引理提供了一种不改变最大公因式的操作，我们将利用这种操作来降低多项式的次数，把问题向简单的方向转化。

🔗

引理 1.3.2.

设

f (x), g (x) \in F [x]

。

🔗

若 $g (x) | f (x),$ 则 $(f (x), g (x)) = c g (x)$ ，其中c为 $g (x)$ 首项系数的倒数；
对任意 $l (x) \in F [x]$ ，成立

$(f (x), g (x)) = (f (x) + l (x) g (x), g (x)) .$

🔗

证明.

只证明项 2。若

(f (x), g (x))

存在，设

(f (x), g (x)) = d (x)

，则

d (x) | f (x)

且

d (x) | g (x)

。由命题 1.2.10得

d (x) | f (x) + l (x) g (x),

故

d (x)

是

f (x) + l (x) g (x)

与

g (x)

的一个公因式。另一方面，若

h (x) | f (x) + l (x) g (x)

且

h (x) | g (x)

，由命题 1.2.10得

h (x) | [f (x) + l (x) g (x)] - l (x) g (x),

则

h (x) | f (x)

且

h (x) | g (x)

。从而

h (x) | d (x)

。根据定义，

(f (x) + l (x) g (x), g (x)) = d (x) .

同理可证：若

(f (x) + l (x) g (x), g (x))

存在，则

(f (x), g (x)) = (f (x) + l (x) g (x), g (x)) .

为了方便叙述，不妨假设

\deg f (x) \geq \deg g (x)

。当

g (x) | f (x)

时，项 1 的结论已经给出了最大公因式。当

g (x) ∤ f (x)

时，做带余除法，设

f (x) = g (x) q (x) + r (x)

，取

l (x) = - q (x)

，则

🔗

(f (x), g (x)) = (f (x) - q (x) g (x), g (x)) = (r (x), g (x)) = (g (x), r (x)) .

于是我们将求

f (x), g (x)

最大公因式的问题转化为求

g (x), r (x)

最大公因式的问题，此时

\deg r (x) < \deg g (x) \leq \deg f (x)

，即在此过程中多项式的总次数严格降低。不断重复上述过程直到我们求出最大公因式。由于每次总次数都严格降低，所以这个过程一定在有限步后转化到项 1 ，即可以求出我们要的最大公因式。上述求最大公因式的方法称为辗转相除法，或 Euclidean算法。

🔗

例 1.3.3. 简单算例，暂缺.

利用辗转相除法，接下来给出最大公因式的一个常用结论。由于这个结论的重要，我们将给出3种不同的证明方法。

🔗

定理 1.3.4. Bézout定理.

设

f (x), g (x) \in F [x]

，则存在

d (x) \in F [x]

，使得

(f (x), g (x)) = d (x)

，且存在

u (x), v (x) \in F [x]

，使

🔗

\begin{matrix} (1.3.1) & d (x) = f (x) u (x) + g (x) v (x) \end{matrix}

🔗

证明.

不妨设

\deg g (x) \leq \deg f (x)

。对

g (x)

的次数使用归纳法。

归纳法的初始情形为

g (x) = 0

。此时容易看到

d (x) = (f (x), g (x)) = {\begin{cases} 0, & 若 f (x) = 0 ； \\ \frac{1}{c} f (x), & 若 f (x) \neq 0 ， c 为 f (x) 首项系数。 \end{cases}

取

u (x) = {\begin{cases} 1, & 若 f (x) = 0 ； \\ \frac{1}{c}, & 若 f (x) \neq 0, c 为 f (x) 首项系数。 \end{cases}

v (x) = 0

，可知此时结论成立。

接下来讨论

g (x) \neq 0

的情况。对

g (x)

的次数使用数学归纳法，假设命题对最低次数小于

g (x)

次数的多项式组结论都成立。

因为

g (x) \neq 0

，根据带余除法知存在

q (x), r (x) \in F [x]

，使得

f (x) = g (x) q (x) + r (x),

其中

\deg r (x) < \deg g (x)

。

根据归纳假设：对于

g (x)

和

r (x)

，存在

u_{1} (x), v_{1} (x) \in F [x]

，使得

\begin{matrix} (1.3.2) & d (x) = u_{1} (x) g (x) + v_{1} (x) r (x), \end{matrix}

其中

d (x) = (g (x), r (x))

。

注意到

\begin{matrix} (1.3.3) & r (x) = f (x) - q (x) g (x), \end{matrix}

根据引理 1.3.2，

d (x) = (f (x) - q (x) g (x), g (x)) = (f (x), g (x)) .

把 (1.3.3)代入 (1.3.2)得

\begin{aligned} d (x) & = u_{1} (x) g (x) + v_{1} (x) r (x) \\ = u_{1} (x) g (x) + v_{1} (x) [f (x) - q (x) g (x)] \\ = v_{1} (x) f (x) + [u_{1} (x) - q (x) v_{1} (x)] g (x), \end{aligned}

取

u (x) = v_{1} (x)

，

v (x) = u_{1} (x) - q (x) v_{1} (x)

，可知结论成立。

证明.

只考虑非平凡的情况，即

f (x) \neq 0

且

g (x) \neq 0

。易知平凡情况下结论成立。

构造集合

I = {f (x) u (x) + g (x) v (x) | u (x), v (x) \in F [x]} .

因为非0多项式的次数都是自然数，所以

I

中必然存在次数最小的非0多项式。同时注意到

I

关于数乘运算封闭，所以

I

中至少存在一个次数最低且首项系数为一的（非0）多项式，记这个多项式为

d (x)

。由于

d (x) \in I

，于是存在

u (x), v (x) \in F [x]

，使得

\begin{matrix} (1.3.4) & d (x) = f (x) u (x) + g (x) v (x) . \end{matrix}

下面我们说明这样取出的

d (x)

就是

(f (x), g (x))

。

先用反证法证明

d (x) | f (x)

且

d (x) | g (x)

。若不然，则

d (x) ∤ f (x)

或

d (x) ∤ g (x)

。不妨设

d (x) ∤ f (x)

，由带余除法，存在

q (x), r (x) \in F [x]

，使得

f (x) = q (x) d (x) + r (x),

其中

0 \leq \deg r (x) < \deg d (x)

。将 (1.3.4) 代入上式得

\begin{array}{ccl} c r (x) & = & c f (x) - c q (x) [f (x) u (x) + g (x) v (x)] \\ = & f (x) [c - c q (x) u (x)] + g (x) [- c q (x) v (x)], \end{array}

其中

c

为

r (x)

首项系数的倒数，故

c r (x)

是

I

中首一多项式且

\deg c r (x) < \deg d (x)

，这与

d (x)

是

I

中次数最低的首一多项式相矛盾。

接下来证明最大公因式定义中的条件2：若

h (x) | f (x)

且

h (x) | g (x)

，根据命题 1.2.10得

h (x) | f (x) u (x) + g (x) v (x),

即

h (x) | d (x)

。

综上，结论成立。

证明.

本证明中也只考虑非平凡的情况，即

f (x) \neq 0

且

g (x) \neq 0

。易知平凡情况下结论成立。

第三种证明方式是用辗转相除法给出一个计算最大公因式和相应

u (x), v (x)

的算法。由带余除法和辗转相除法，我们有下列等式：

\begin{matrix} f (x) = g (x) q_{1} (x) + r_{1} (x), \\ g (x) = r_{1} (x) q_{2} (x) + r_{2} (x), \\ r_{1} (x) = r_{2} (x) q_{3} (x) + r_{3} (x), \\ \dots \dots \dots \dots \dots \dots \dots \dots \\ r_{i - 2} (x) = r_{i - 1} (x) q_{i} (x) + r_{i} (x), \\ \dots \dots \dots \dots \dots \dots \dots \dots \end{matrix}

这里

\deg g (x) > \deg r_{1} (x) > \deg r_{2} (x) > \deg r_{3} (x) > \dots

，因此经过有限步后，必有一个等式的余式为零。不妨设

r_{s + 1} (x) = 0

，则

\begin{matrix} (1.3.5) & \begin{matrix} f (x) = g (x) q_{1} (x) + r_{1} (x), \\ g (x) = r_{1} (x) q_{2} (x) + r_{2} (x), \\ r_{1} (x) = r_{2} (x) q_{3} (x) + r_{3} (x), \\ \dots \dots \dots \dots \dots \dots \dots \dots \\ r_{s - 3} (x) = r_{s - 2} (x) q_{s} (x) + r_{s - 1} (x), \\ r_{s - 2} (x) = r_{s - 1} (x) q_{s} (x) + r_{s} (x), \\ r_{s - 1} (x) = r_{s} (x) q_{s + 1} (x) . \end{matrix} \end{matrix}

由引理 1.3.2 第一个结论可得

(r_{s - 1} (x), r_{s} (x)) = c r_{s} (x)

，其中

c

为

r_{s} (x)

首项系数的倒数。根据引理 1.3.2 第二个结论，

\begin{aligned} (r_{s - 1} (x), r_{s} (x)) & = (r_{s - 2} (x), r_{s - 1} (x)) \\ = \dots \\ = (r_{2} (x), r_{1} (x)) \\ = (r_{1} (x), g (x)) \\ = (g (x), f (x)), \end{aligned}

因此

(f (x), g (x)) = c r_{s} (x)

存在。由 (1.3.5)倒数第二个式子可得

r_{s} (x) = r_{s - 2} (x) - r_{s - 1} (x) q_{s} (x) .

由(1.3.5)倒数第三个式子得

r_{s - 1} (x) = r_{s - 3} (x) - r_{s - 2} (x) q_{s - 1} (x),

代入上式，有

\begin{array}{ccl} r_{s} (x) & = & r_{s - 2} (x) - [r_{s - 3} (x) - r_{s - 2} (x) q_{s - 1} (x)] q_{s} (x) \\ = & r_{s - 3} (x) [- q_{s} (x)] + r_{s - 2} (x) [1 + q_{s - 1} (x) q_{s} (x)] . \end{array}

依此类推，将(1.3.5)中等式逐步向下而上代入，可得

u_{1} (x), v_{1} (x) \in F [x]

，使得

r_{s} (x) = f (x) u_{1} (x) + g (x) v_{1} (x) .

令

u (x) = c u_{1} (x), v (x) = c v_{1} (x)

，则

(f (x), g (x)) = f (x) u (x) + g (x) v (x) .

(1.3.1) 称为 Bézout等式。

🔗

上面的3种证明本质上是相同的。第1种证明使用了数学归纳法，算法实现上需要使用递归；第2种证明中反证法部分实际上可以对应一种迭代算法，每次迭代后产生的多项式次数都严格下降，直到达到最小次数多项式（或者说下次迭代产生0多项式）为止；第3种方法适合于手动计算。请同学们比较理解。

🔗

来看一个具体的例子。在例子中，我们用第3种方法算出Bézout等式的系数。

🔗

例 1.3.5.

设

f (x) = 6 x^{5} + 4 x^{4} + 7 x^{3} + 8 x^{2} + 10 x + 7, g (x) = 3 x^{4} - x^{3} + 3 x^{2} + 4,

，求

u (x), v (x)

，使得

d (x) = f (x) u (x) + g (x) v (x) .

解答.

手工计算最大公因式及相应的

u (x), v (x)

可以使用下面的计算格式。

\begin{array}{rrrrrrrrrrrrl} q_{2} (x) = x - 1 & 3 x^{4} & - x^{3} & + 3 x^{2} & + 4 & 6 x^{5} & + 4 x^{4} & + 7 x^{3} & + 8 x^{2} & + 10 x & + 7 & 2 x + 2 = q_{1} (x) \\ 3 x^{4} & + 2 x^{3} & + 2 x^{2} & - x & 6 x^{5} & - 2 x^{4} & + 6 x^{3} & + 8 x \\ - 3 x^{3} & + x^{2} & + x & + 4 & 6 x^{4} & + x^{3} & + 8 x^{2} & + 2 x & + 7 \\ - 3 x^{3} & - 2 x^{2} & - 2 x & + 1 & 6 x^{4} & - 2 x^{3} & + 6 x^{2} & + 8 \\ r_{2} (x) & = 3 x^{2} & + 3 x & + 3 & r_{1} (x) & = 3 x^{3} & + 2 x^{2} & + 2 x & - 1 & x - \frac{1}{3} = q_{3} (x) \\ 3 x^{3} & + 3 x^{2} & + 3 x \\ - x^{2} & - x & - 1 \\ - x^{2} & - x & - 1 \\ r_{3} (x) & = 0 \end{array}

所以

(f (x), g (x)) = \frac{1}{3} r_{2} (x) = x^{2} + x + 1.

又

\begin{array}{ccl} r_{2} (x) & = & g (x) - r_{1} (x) q_{2} (x) \\ = & g (x) - [f (x) - g (x) q_{1} (x)] q_{2} (x) \\ = & f (x) [- q_{2} (x)] + g (x) [1 + q_{1} (x) q_{2} (x)], \end{array}

因此

u (x) = - \frac{1}{3} q_{2} (x) = - \frac{1}{3} x + \frac{1}{3}, v (x) = \frac{1}{3} [1 + q_{1} (x) q_{2} (x)] = \frac{2}{3} x^{2} - \frac{1}{3} .

与定理 1.3.4的第2种证明相对应，我们有下面的结论。

🔗

定理 1.3.6.

d (x)

是

f (x), g (x)

的最大公因子等价于

🔗

$d (x) | f (x)$ ， $d (x) | g (x)$ ；
存在 $u (x), v (x) \in F [x]$ ，使得

$d (x) = u (x) f (x) + v (x) g (x) .$

🔗

例 1.3.7.

设

f (x), g (x) \in F [x]

，

n \in Z^{+}

，

d (x) = (f (x), g (x))

。证明：

d (x^{n}) = (f (x^{n}), g (x^{n})) .

解答.

由已知条件知

d (x) | f (x), d (x) | g (x)

，所以存在

h (x), k (x) \in F [x]

，使得

f (x) = d (x) h (x), g (x) = d (x) k (x) .

用

x^{n}

代替

x

，得

f (x^{n}) = d (x^{n}) h (x^{n}), g (x^{n}) = d (x^{n}) k (x^{n}),

因而

d (x^{n}) | f (x^{n}), d (x^{n}) | g (x^{n})

。

另一方面，由定理 1.3.6，存在

u (x), v (x) \in F [x]

，使得

d (x) = u (x) f (x) + v (x) g (x) .

用

x^{n}

代替

x

，得

d (x^{n}) = u (x^{n}) f (x^{n}) + v (x^{n}) g (x^{n}) .

由定理 1.3.4，

d (x)

是

f (x), g (x)

的一个最大公因式。又

d (x^{n})

是首一多项式，因此

d (x^{n}) = (f (x^{n}), g (x^{n}))

。

思考：最大公因式与数域有关吗？

🔗

最大公因式的定义可以推广到多个多项式。

🔗

定义 1.3.8.

对

m

个多项式

f_{i} (x) \in F [x] (i = 1, 2, \dots, m)

，若存在

d (x) \in F [x]

，使得

🔗

$d (x) | f_{i} (x) (i = 1, 2, \dots, m)$ ；
若 $h (x) | f_{i} (x) (i = 1, 2, \dots, m)$ ，则 $h (x) | d (x)$ ；

则称

d (x)

是

f_{i} (x) (i = 1, 2, \dots, m)

的最大公因式，其中首一的最大公因式记为：

🔗

(f_{1} (x), f_{2} (x), \dots, f_{m} (x)) .

🔗

在计算多个多项式的最大公因式时，通常我们采取两个两个求最大公因式的方式，我们以三个多项式为例来说明问题。

🔗

命题 1.3.9.

设

f (x), g (x), h (x) \in F [x]

，则

🔗

\begin{aligned} (f (x), g (x), h (x)) & = ((f (x), g (x)), h (x)) \\ = (f (x), (g (x), h (x))) . \end{aligned}

🔗

证明.

设

(f (x), g (x)) = d_{1} (x), (d_{1} (x), h (x)) = d (x)

，则

d (x) | d_{1} (x), d (x) | h (x), d_{1} (x) | f (x), d_{1} (x) | g (x),

由此推出

d (x) | f (x), d (x) | g (x), d (x) | h (x) .

另一方面，若

k (x) | f (x), k (x) | g (x), k (x) | h (x)

，由

d_{1} (x) = (f (x), g (x))

得

k (x) | d_{1} (x) .

注意到

k (x) | d_{1} (x), k (x) | h (x)

，所以

k (x) | (d_{1} (x), h (x)),

即

k (x) | d (x)

。因此

d (x)

是

f (x), g (x), h (x)

的一个最大公因式。又

d (x)

是首一多项式，故

(f (x), g (x), h (x)) = d (x) .

同理可得另一等式。

上述命题的结论可以推广到多个多项式。该结论表明：求多个多项式的最大公因式时，可先求任意两个多项式的最大公因式，再用同样方法继续，而不必顾及先后顺序。

🔗

子节 1.3.2 互素

两个多项式的最大公因式为0次多项式是一种极端情况，这种极端情况有很多很好的性质，具有特殊意义，有必要单独研究。

🔗

定义 1.3.10.

设

f (x), g (x) \in F [x]

，若

(f (x), g (x)) = 1

，则称

f (x)

与

g (x)

互素或互质。

🔗

由定理 1.3.4和定理 1.3.6可得如下一个常用结论。

🔗

定理 1.3.11.

设

f (x), g (x) \in F [x]

，则

f (x), g (x)

互素的充要条件是存在

u (x), v (x) \in F [x]

，使得

🔗

f (x) u (x) + g (x) v (x) = 1.

🔗

一般的，若仅有

d (x) = f (x) u (x) + g (x) v (x)

，并不能保证

d (x) = (f (x), g (x))

。但若

u (x) f (x) + v (x) g (x) = 1

，就可以确保

(f (x), g (x)) = 1

。

🔗

下面是互素多项式具有的一些好性质。请注意思考，当没有互素条件时命题不成立的原因是什么，并尝试给出相应的反例。

🔗

命题 1.3.12.

设

f_{1} (x) | g (x)

，

f_{2} (x) | g (x)

，且

(f_{1} (x), f_{2} (x)) = 1

，则

🔗

f_{1} (x) f_{2} (x) | g (x) .

🔗

证明.

因为

(f_{1} (x), f_{2} (x)) = 1

，所以存在

u (x), v (x) \in F [x]

，使得

f_{1} (x) u (x) + f_{2} (x) v (x) = 1.

因而

\begin{matrix} (1.3.6) & g (x) f_{1} (x) u (x) + g (x) f_{2} (x) v (x) = g (x) . \end{matrix}

由

f_{1} (x) | g (x)

，

f_{2} (x) | g (x)

可知，存在

s (x), t (x) \in F [x]

，使得

g (x) = f_{1} (x) s (x), g (x) = f_{2} (x) t (x) .

代入 (1.3.6)，得

\begin{array}{ccl} g (x) & = & g (x) f_{1} (x) u (x) + g (x) f_{2} (x) v (x) \\ = & f_{2} (x) t (x) f_{1} (x) u (x) + f_{1} (x) s (x) f_{2} (x) v (x) \\ = & f_{1} (x) f_{2} (x) [t (x) u (x) + s (x) v (x)] . \end{array}

因此

f_{1} (x) f_{2} (x) | g (x)

。

命题 1.3.13.

设

f (x) | g (x) h (x)

，且

(f (x), g (x)) = 1

，则

🔗

f (x) | h (x) .

🔗

证明.

因为

(f (x), g (x)) = 1

，所以存在

u (x), v (x) \in F [x]

，使得

f (x) u (x) + g (x) v (x) = 1.

两边同乘

h (x)

，得

f (x) h (x) u (x) + g (x) h (x) v (x) = h (x) .

由于

f (x) | g (x) h (x)

，所以由命题 1.2.10，有

f (x) | h (x)

。

命题 1.3.14.

设

(f_{1} (x), g (x)) = 1

，

(f_{2} (x), g (x)) = 1

，则

🔗

(f_{1} (x) f_{2} (x), g (x)) = 1.

🔗

证明.

根据定理 1.3.4，存在

u_{1} (x), v_{1} (x), u_{2} (x), v_{2} (x) \in F [x]

，使得

f_{1} (x) u_{1} (x) + g (x) v_{1} (x) = 1, f_{2} (x) u_{2} (x) + g (x) v_{2} (x) = 1.

两式相乘，得

[f_{1} (x) f_{2} (x)] u (x) + g (x) v (x) = 1,

其中

u (x) = u_{1} (x) u_{2} (x),

v (x) = f_{1} (x) u_{1} (x) v_{2} (x) + f_{2} (x) u_{2} (x) v_{1} (x) + g (x) v_{1} (x) v_{2} (x) .

因此

(f_{1} (x) f_{2} (x), g (x)) = 1

。

命题 1.3.15.

设

(f (x), g (x)) = d (x) \neq 0

，且

f (x) = f_{1} (x) d (x)

，

g (x) = g_{1} (x) d (x)

，则

(f_{1} (x), g_{1} (x)) = 1

。

🔗

证明.

根据定理 1.3.4，存在

u (x), v (x) \in F [x]

，使得

f (x) u (x) + g (x) v (x) = d (x) .

将

f (x) = f_{1} (x) d (x)

，

g (x) = g_{1} (x) d (x)

代入得

[f_{1} (x) u (x) + g_{1} (x) v (x)] d (x) = d (x) .

因

d (x) \neq 0

，所以由消去律得

f_{1} (x) u (x) + g_{1} (x) v (x) = 1.

因此

(f_{1} (x), g_{1} (x)) = 1

。

🔗

子节 1.3.3 最小公倍式

最小公倍式是与最大公因式相对应的一个概念，二者之间有着密切联系。

🔗

定义 1.3.16.

设

f (x), g (x) \in F [x]

。若

m (x) \in F [x]

，使得

🔗

$f (x) | m (x)$ 且 $g (x) | m (x)$ ；
只要 $f (x) | l (x)$ 且 $g (x) | l (x)$ ，就有 $m (x) | l (x)$ ，

则称

m (x)

是

f (x)

与

g (x)

的最小公倍式 (l.c.m.)。首一最小公倍式记作

[f (x), g (x)]

。

🔗

特别约定

[0, 0] = 0

。类似于最大公因式，最小公倍式也可以推广到多个多项式的情形。特别地，

f_{1} (x), \dots, f_{m} (x)

的首一最小公倍式记为

🔗

[f_{1} (x), \dots, f_{m} (x)] .

🔗

最小公倍式和最大公因式之间的关系可以由下述结论描述。

🔗

命题 1.3.17.

设

f (x), g (x) \in F [x]

，则

🔗

f (x) g (x) = c (f (x), g (x)) [f (x), g (x)],

其中

c

为

f (x)

和

g (x)

首项系数的乘积。

🔗

子节 1.3.4 孙子定理/中国剩余定理*

作为辗转相除法和最大公因式的一个应用，这里我们简要介绍一个著名定理——孙子定理的结论和证明。孙子定理也称为中国剩余定理，是求解同余方程组的一般方法。同余方程组的相关问题会在后续课程《抽象代数》中进一步展开。

🔗

在《孙子算经》一书中有一道著名的“孙子问题”：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”用现代的数学语言翻译过来，孙子问题也可叙述为：现有一个未知整数

x

，

x

除以3的余数为2，除以5的余数为3，除以7的余数为2，问

x

是多少？

🔗

把这个问题推广到多项式：假设现有一组两两互素的多项式

p_{1} (x), \dots, p_{m} (x)

(m \geq 2)

，我们知道一个多项式

g (x)

分别除以

p_{1} (x), \dots, p_{m} (x)

的余式，问满足条件的多项式

g (x)

是否存在？若存在，该如何求

g (x)

？孙子定理回答了

g (x)

的存在性问题，其证明过程给出了

g (x)

的求法。

🔗

为证明一般结论，我们先来看一个简单的特殊情形。

🔗

引理 1.3.18.

设

p_{1} (x), \dots, p_{m} (x) \in F [x] (m \geq 2)

两两互素，则存在

f_{i} (x) \in F [x] (i = 1, \dots, m)

，使得对任意

i, j = 1, \dots, m

且

i \neq j

，都有

🔗

f_{i} (x) = l_{i} (x) p_{i} (x) + 1, f_{i} (x) = h_{i j} (x) p_{j} (x) .

🔗

证明.

因为当

i \neq j

时，

(p_{i} (x), p_{j} (x)) = 1

，所以

(p_{i} (x), \prod_{j \neq i, j = 1}^{m} p_{j} (x)) = 1.

根据定理 1.3.4存在

u_{i} (x), v_{i} (x) \in F [x]

，使得

p_{i} (x) u_{i} (x) + [\prod_{j \neq i, j = 1}^{m} p_{j} (x)] v_{i} (x) = 1.

令

f_{i} (x) = [\prod_{j \neq i, j = 1}^{m} p_{j} (x)] v_{i} (x)

，则结论成立。

定理 1.3.19. 孙子定理.

设

p_{1} (x), \dots, p_{m} (x) \in F [x] (m \geq 2)

两两互素，

g_{1} (x), \dots, g_{m} (x) \in F [x]

且

\deg g_{i} (x) < \deg p_{i} (x)

，则存在唯一多项式

g (x)

，使得对任意

i = 1, \dots, m

，有

🔗

g (x) = p_{i} (x) q_{i} (x) + g_{i} (x),

且

\deg g (x) < \sum_{i = 1}^{m} \deg p_{i} (x)

。

🔗

证明.

由引理 1.3.18，存在

f_{i} (x) (i = 1, \dots, m)

，使得对任意

i, j = 1, \dots, m

且

i \neq j

，都有

\begin{matrix} (1.3.7) & f_{i} (x) = l_{i} (x) p_{i} (x) + 1, f_{i} (x) = h_{i j} (x) p_{j} (x) . \end{matrix}

令

f (x) = \sum_{i = 1}^{m} f_{i} (x) g_{i} (x)

，将 (1.3.7)代入得

\begin{array}{ccl} f (x) & = & f_{i} (x) g_{i} (x) + \sum_{j \neq i, j = 1}^{m} f_{j} (x) g_{j} (x) \\ = & [g_{i} (x) l_{i} (x) p_{i} (x) + g_{i} (x)] + \sum_{j \neq i, j = 1}^{m} [h_{j i} (x) p_{i} (x)] g_{j} (x) \\ = & p_{i} (x) [g_{i} (x) l_{i} (x) + \sum_{j \neq i, j = 1}^{m} h_{j i} (x) g_{j} (x)] + g_{i} (x) . \end{array}

根据带余除法，存在

q (x), g (x) \in F [x]

，使得

f (x) = [\prod_{i = 1}^{m} p_{i} (x)] q (x) + g (x),

其中

\deg g (x) < \deg [\prod_{i = 1}^{m} p_{i} (x)] = \sum_{i = 1}^{m} \deg p_{i} (x)

。则

g (x) = p_{i} (x) [g_{i} (x) l_{i} (x) + \sum_{j \neq i, j = 1}^{m} h_{j i} (x) g_{j} (x) - q (x) \prod_{j \neq i, j = 1}^{m} p_{j} (x)] + g_{i} (x) .

记

q_{i} (x) = g_{i} (x) l_{i} (x) + \sum_{j \neq i, j = 1}^{m} h_{j i} (x) g_{j} (x) - q (x) \prod_{j \neq i, j = 1}^{m} p_{j} (x)

，则

g (x) = p_{i} (x) q_{i} (x) + g_{i} (x) .

再证明唯一性。若存在

g (x), h (x) \in F [x]

，使得

g (x) = p_{i} (x) q_{i} (x) + g_{i} (x), h (x) = p_{i} (x) t_{i} (x) + g_{i} (x),

且

\deg g (x) < \sum_{i = 1}^{m} \deg p_{i} (x), \deg h (x) < \sum_{i = 1}^{m} \deg p_{i} (x)

。则

g (x) - h (x) = p_{i} (x) [q_{i} (x) - t_{i} (x)],

即

p_{i} (x) | g (x) - h (x)

。注意到

p_{1} (x), p_{2} (x), \dots, p_{m} (x)

两两互素，所以

\prod_{i = 1}^{m} p_{i} (x) | g (x) - h (x) .

而

\begin{aligned} \deg [g (x) - h (x)] & \leq max {\deg g (x), \deg h (x)} \\ < \sum_{i = 1}^{m} \deg p_{i} (x) \\ = \deg [\prod_{i = 1}^{m} p_{i} (x)], \end{aligned}

故

g (x) - h (x) = 0

，即此时

g (x)

是唯一的。

例 1.3.20.

求一个次数最低的多项式

g (x)

，使

x^{2} - 1, x^{3} + x^{2} - x - 2

除

g (x)

的余式分别为

x, x^{2} - 1

。

解答.

因为

(x^{2} - 1) (x + 1) - (x^{3} + x^{2} - x - 2) = 1,

所以由引理 1.3.18知可取

f_{1} (x) = - (x^{3} + x^{2} - x - 2), f_{2} (x) = (x^{2} - 1) (x + 1) .

由孙子定理证明知，令

\begin{array}{ccl} f (x) & = & x f_{1} (x) + (x^{2} - 1) f_{2} (x) \\ = & x^{5} - 3 x^{3} - x^{2} + 3 x + 1, \end{array}

则

x^{2} - 1, x^{3} + x^{2} - x - 2

除

f (x)

的余式分别为

x, x^{2} - 1

。由带余除法，

f (x) = (x^{2} - 1) (x^{3} + x^{2} - x - 2) + (- x^{4} - x^{3} + 2 x^{2} + 2 x - 1),

取

g (x) = - x^{4} - x^{3} + 2 x^{2} + 2 x - 1

，则

g (x)

是满足条件次数最低的多项式。

下面我们利用孙子定理来证明一个重要结论。

🔗

定理 1.3.21.

设

x_{0}, \dots, x_{n}, y_{0}, \dots, y_{n} \in F

。若对

\forall i \neq j

，

x_{i} \neq x_{j}

，则存在唯一一个次数不超过

n

的多项式

f (x) \in F [x]

，使得对

\forall i \in [n + 1]

，

f (x_{i}) = y_{i}

。

🔗

证明.

令

p_{i} (x) = x - x_{i}

，

i = 0, \dots, n

。因为

x_{0}, \dots, x_{n}

两两不同，所以

p_{0} (x), \dots, p_{n} (x)

两两互素。根据定理 1.3.19，存在唯一一个多项式

f (x)

，使得对任意

i \in [n + 1]

，

f (x) = p_{i} (x) q_{i} (x) + y_{i},

且

\deg f (x) < \sum_{i = 0}^{n} \deg p_{i} (x) = n + 1

，即存在唯一一个次数不超过

n

的多项式

f (x) \in F [x]

，使得对

\forall i \in [n + 1]

，

f (x_{i}) = y_{i}

。

利用定理 1.3.21可以回答之前遗留的一个问题，即多项式作为表达式相等和作为函数相等二者的等价性问题。

🔗

定理 1.3.22.

设

🔗

f (x) = a_{n} x^{n} + \dots + a_{0},

g (x) = b_{m} x^{m} + \dots + b_{0}

是

F [x]

中的两个多项式，其中

F \subseteq C

是复数域的子域。则下述两个命题等价：

🔗

$f (x) = g (x)$ ，即 $m = n$ 且 $a_{i} = b_{i}, i = 0, \dots, n$ ；
对任意的 $c \in F$ ， $f (c) = g (c)$ 均成立。

🔗

证明.

只需证明2可以推出1成立。不妨设

m \leq n

，则

f (x), g (x)

均是次数不超过

n

的多项式。

因为

F

是复数域的子域，所以

Q \subseteq F

(命题 1.1.4)，于是可以在

F

中找到

n + 1

个不同的数，记为

x_{0}, \dots, x_{n}

。进一步地，记

y_{i} = f (x_{i}), i = 0, \dots, n

。则根据命题2可知

g (x_{i}) = y_{i}, i = 0, \dots, n

也成立。

跟据定理 1.3.21中满足条件多项式的唯一性，可知

f (x) = g (x)

，即命题1成立。

备注 1.3.23.

定理 1.3.22的条件中要求

F \subseteq C

，这是为了保证

F

是无限域。在后续课程《抽象代数》中，除复数域

C

的子域外，还有很多其它的域。其中较为有代表性的就是有限域

Z_{p}

。当系数域

F

为有限域时，多项式的表达式相等与函数相等就不再等价了。有兴趣的同学可以搜索一下相关的知识。

🔗

具体的，多项式表达式

🔗

f (x) = \sum_{i = 0}^{n} y_{i} F_{i} (x) = \sum_{i = 0}^{n} y_{i} \prod_{j \neq i} \frac{x - x_{j}}{x_{i} - x_{j}}

也称为Lagrange插值多项式。对于给定的

x_{0}, \dots, x_{n}, y_{0}, \dots, y_{n}

，此多项式

f (x)

就是满足条件

y_{i} = f (x_{i}), i = 0, \dots, n

的多项式。

🔗

当

n = 1

时，

(x_{0}, y_{0})

和

(x_{1}, y_{1})

对应于坐标平面中的两个点，此时Lagrange插值多项式则对应于一条直线方程，即此时定理 1.3.21等价于初等几何里的一个常用事实：平面中的两个不同点确定一条直线。（

x_{0} \neq x_{1}

相当于排除了所确定的直线垂直于

x

轴这种特殊情况。）

🔗

一般的，定理 1.3.21也可以简略叙述为：

x o y

平面上

n + 1

个横坐标互不相同的点可以与次数不超过

n

的多项式一一对应。于是，在选定

x_{0}, \dots, x_{n}

的前提下，次数不超

n

的多项式也可用序列

(y_{0}, \dots, y_{n})

表示，这种表示方式称为多项式的值表示。

🔗

例 1.3.24. 多项式系数表示与值表示的关系.

取定

x_{0} = 1, x_{1} = - 1

时，次数不超过1的多项式值表示

(y_{0}, y_{1})

和系数表示

a_{0} + a_{1} x

可以通过下面的关系式进行换算：

{\begin{cases} y_{0} = a_{0} + a_{1} \\ y_{1} = a_{0} - a_{1} \end{cases} {\begin{cases} a_{0} = \frac{1}{2} (y_{0} + y_{1}) \\ a_{1} = \frac{1}{2} (y_{0} - y_{1}) \end{cases}

取定

x_{0} = 1, x_{1} = i, x_{2} = - 1, x_{3} = - i

（其中

i^{2} = - 1

）时，次数不超过3的多项式值表示

(y_{0}, y_{1}, y_{2} ， y_{3})

和系数表示

a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}

可以通过下面的关系式进行换算：

{\begin{cases} y_{0} = a_{0} + a_{1} + a_{2} + a_{3} \\ y_{1} = a_{0} + a_{1} i - a_{2} - a_{3} i \\ y_{2} = a_{0} - a_{1} + a_{2} - a_{3} \\ y_{3} = a_{0} - a_{1} i - a_{2} + a_{3} i \end{cases} {\begin{cases} a_{0} = \frac{1}{4} (y_{0} + y_{1} + y_{2} + y_{3}) \\ a_{1} = \frac{1}{4} (y_{0} - y_{1} i - y_{2} + y_{3} i) \\ a_{2} = \frac{1}{4} (y_{0} - y_{1} + y_{2} - y_{3}) \\ a_{1} = \frac{1}{4} (y_{0} + y_{1} i - y_{2} - y_{3} i) \end{cases}

请同学们观察其中的规律。

设

f (x), g (x), h (x)

都是次数不超过

n

的多项式，且

h (x) = f (x) g (x)

。给定

x_{0}, \dots, x_{n}

，若

f (x)

的值表示为

(y_{0}, \dots, y_{n})

，

g (x)

的值表示为

(z_{0}, \dots, z_{n})

，则可知

h (x)

的值表示为

(y_{0} z_{0}, \dots, y_{n} z_{n})

。

🔗

总结一下：多项式有两种常用的表示方式，系数表示和值表示。系数表示较为直观、简洁，直接对应函数表达式，可以利用函数表达式算出任意一点的函数值；对于值表示的多项式，除了给定的点外，其它点的函数值往往还需要转化为系数表示法所对应的函数表达式来求，但值表示在计算多项式乘法时有较为明显的优势。著名的离散Fourier变换（DFT）实现的就是这两种表示方法之间的转化，有兴趣的同学可以搜索相关的材料做进一步的了解。这个问题后续我们还会进一步涉及到。

🔗

子节 1.3.5 Sage相关

接下来我们用sage代码来实践一下本节中学到的内容。

🔗

Sage中直接提供的计算最大公因式的命令为gcd()，命令名gcd来自于“最大公因式”的英文名称 “greatest common divisor”。

🔗

xxxxxxxxxx
 
pretty_print_default(True);
P.<x> = PolynomialRing(QQ);
f = 6*x^5+4*x^4+7*x^3+8*x^2+10*x+7;
g = 3*x^4-x^3+3*x^2+4;
gcd(f,g),f.gcd(g)

3个以上多项式的最大公因式也可以用gcd()命令来求。

🔗

xxxxxxxxxx
 
h = x^3-1;
gcd([f,g,h])

Sage中可以使用xgcd()命令获得定理 1.3.4中的最大公因式

d (x)

和

u (x), v (x)

。

🔗

xxxxxxxxxx
 
xgcd(f,g)

xxxxxxxxxx
 
f.xgcd(g)

和gcd()命令不同的是xgcd()不支持3个及以上的多项式。

🔗

为加深对定理 1.3.4的理解，我们给出这个定理前两种证明算法实现的代码。

🔗

xxxxxxxxxx
 
def ex_gcd_re(f,g):
  """
  用递归算法计算并返回Bézout等式中d,u,v 
  当直接输入f为常数时本程序会报错，因为直接输入的常数不会被识别为多项式，故无法调用与多项式相关的函数。
  """
  if g == 0:
      if f != 0:
          d = f.monic();
          #取d为与f相伴的首一多项式
          u = 1/f.leading_coefficient();
          #leading coefficient是首项系数
          v = 0;
      else:
          d,u,v = 0,0,0;
  else: # g != 0
      q,r = f.quo_rem(g);
      d,u1,v1 = ex_gcd_re(g,r); 
      # 递归调用函数，相当于第一种证明中使用归纳法的一步
      u = v1;
      v = u1 - q*v1;
  return d,u,v
​
#算例
pretty_print_default(True);
P.<x> = PolynomialRing(QQ);
f = 6*x^5+4*x^4+7*x^3+8*x^2+10*x+7;
g = 3*x^4-x^3+3*x^2+4;
ex_gcd_re(f,g)

xxxxxxxxxx
 
def ex_gcd_nore(f,g):
  """
  利用非递归算法计算Bézout等式中d,u,v的函数
  """
  u, u1, v, v1 = 1, 0, 0, 1;
  while g != 0:
      d = g;
      q, f, g = f // g, g, f % g;
      u, u1 = u1, u - q * u1;
      v, v1 = v1, v - q * v1;
  if d != 0:
      c = d.leading_coefficient();
      d,u,v = d/c,u/c,v/c;
  return d, u, v
#算例
ex_gcd_nore(f,g)

Sage中求最小公倍式的命令为lcm()，命令名来源于“最小公倍式”的英文名称“least common multiple”。

🔗

xxxxxxxxxx
 
f.lcm(g),lcm(f,g)

🔗

练习 1.3.6 练习

基础题.

1.

设

f (x) = x^{4} + 3 x^{3} - x^{2} - 4 x - 3, g (x) = 3 x^{3} + 10 x^{2} + 2 x - 3

，求

(f (x), g (x))

，并求

u (x), v (x)

，使得

(f (x), g (x)) = u (x) f (x) + v (x) g (x)

。

🔗

2.

设

f (x) = x^{3} + (1 + a) x^{2} + 2 x + 2 b, g (x) = x^{3} + a x^{2} + b

的最大公因式是一个二次多项式，求

a, b

的值。

🔗

3.

设

f (x), g (x)

是数域

F

上非零多项式，证明：

f (x)

与

g (x)

不互素的充分必要条件是存在非零多项式

u (x), v (x)

，使得

🔗

u (x) f (x) = v (x) g (x),

其中

\deg u (x) < \deg g (x), \deg v (x) < \deg f (x)

。

🔗

4.

设

f (x), g (x) \in F [x]

，证明下面几点等价：

🔗

$(f (x), g (x)) = 1$ ；
$(f (x), f (x) + g (x)) = 1$ ；
$(g (x), f (x) + g (x)) = 1$ ；
$(f (x) g (x), f (x) + g (x)) = 1$ 。

🔗

5.

*求一个次数最低的多项式

f (x)

，使

f (x)

除以

x^{2} + 1, x^{3} + x^{2} + 1

的余式分别为

x + 1, x^{2} - 1

。

🔗

提高题.

6.

设

t (x)

是首一多项式，

(f (x), g (x)) = d (x)

，则

🔗

(f (x) t (x), g (x) t (x)) = d (x) t (x) .

🔗

7.

设

f_{1} (x) = a f (x) + b g (x), g_{1} (x) = c f (x) + d g (x)

，且

a d - b c \neq 0

，证明：

🔗

(f (x), g (x)) = (f_{1} (x), g_{1} (x)) .

🔗

8.

设

m, n

是正整数，证明：

🔗

(x^{m} - 1, x^{n} - 1) = x^{d} - 1,

其中

d

是

m, n

的最大公因数。

🔗

9.

设

f_{1} (x), \dots, f_{m} (x) \in F [x]

，证明：存在

u_{1} (x), \dots, u_{m} (x) \in F [x]

，使得

🔗

\begin{matrix} (1.3.8) & (f_{1} (x), \dots, f_{m} (x)) = u_{1} (x) f_{1} (x) + \dots + u_{m} (x) f_{m} (x) . \end{matrix}

🔗

10.

设

f (x), g_{1} (x), g_{2} (x), g_{3} (x) \in F [x]

。若

g_{i} (x) | f (x), i = 1, 2, 3

，试问下列命题是否成立，并说明理由：

🔗

如果 $g_{1} (x), g_{2} (x), g_{3} (x)$ 两两互素，那么一定有 $g_{1} (x) g_{2} (x) g_{3} (x) | f (x)$ ；
如果 $g_{1} (x), g_{2} (x), g_{3} (x)$ 互素，那么一定有 $g_{1} (x) g_{2} (x) g_{3} (x) | f (x)$ 。