辗转相除法

                     

贡献者： 零穹; addis

　　¹本节将证明最大公因式的存在性，并介绍最大公因式的算法程序——辗转相除法。简单来说，所谓的辗转相除法是指多次利用带余除法计算两个多项式的最大公因式的算法。

　　 推荐的拓展阅读：欧几里得环。简单来说，这是一种 “能做辗转相除法” 的环²。

1. 最大公因式的存在性

　　 为证明最大公因式的存在，我们先来证明下面一个定理。

　　 证明：1.$\phi(x)|g(x),\phi(x)|f(x)\Rightarrow \phi(x)|g(x),\phi(x)|r(x)$ 的证明：

　　 因为 $\phi(x)|g(x),\phi(x)|f(x)$，由整除的性质 3 多项式的整除，$\phi(x)$ 必整除 $f(x),g(x)$ 的组合

　　 2.$\phi(x)|g(x),\phi(x)|r(x)\Rightarrow\phi(x)|g(x),\phi(x)|f(x)$ 的证明：同样有整除的性质 3，立即证得。

　　 下面利用式 1 来证明最大公因式的存在性，该证明方法便是辗转相除法。

　　 证明：如果 $f(x)$ 和 $g(x)$ 中有一个为 0，比如 $g(x)=0$，那么另一个 $f(x)$ 就是 $f(x)$ 与 $g(x)$ 的最大公因式，且 $f(x)=1\cdot f(x)+1\cdot0$。

　　 以下只需考虑 $g(x)\neq 0$。由带余除法，有

只考虑 $r_1(x)\neq 0$，否则 $g(x)$ 便是最大公因式。再用 $r_1(x)$ 除 $g(x)$，得 同样只考虑 $r_2(x)\neq0$，再用 $r_2(x)$ 除 $r_1(x)$，得 如此不断重复该过程，所得余式的次数就不断降低，即 这样经过有限次相除之后，必然有余式为 0。于是得到一等式： 其中 $r_s(x)$ 是 $r_s(x)$ 与 $r_{s-1}(x)$ 的一个最大公因式。由定理 1 ，$r_s(x)$ 也是 $r_{s-1}(x)$ 与 $r_{s-2}(x)$ 的一个最大公因式。照此逐步推上去，便有 $r_s(x)$ 是 $f(x)$ 和 $g(x)$ 的一个最大公因式。这就证明了最大公因式的存在性。

　　 下面来证明式 3 .由式 8 倒数第二式

这就是说，每一个 $r_i$ 都可由只带 $r_{i-2}$ 和 $r_{i-1}$ 的项表示。若令 $g(x)=r_0(x),f(x)=r_{-1}(x)$，则显然所有的 $r_i$ 最终都可由只带 $g(x)$ 和 $f(x)$ 的项表示，即得式 3 。

2. 互素

　　 两个多项式的最大公因式的存在，使我们能够定义互素 的概念。这和整数中的互素的概念一样，都是指两个对象（这个对象在数论里就是整数）的最大公因式（对于整数叫公因子）为 1.

　　 由整除的性质 1，或由词条的例 1 前一段指出的，可知若两个多项式互素，那么它们的公因式只能是零次多项式。

　　 将互素的概念与最大公因式存在定理相结合，就有下面几个有用的推论。

　　 证明：定理 2 可以直接得出必要性。现在来证明充分性，设存在 $u(x),v(x)$ 使得

并且 $\phi(x)$ 是 $f(x)$ 与 $g(x)$ 的一个最大公因式。于是就有 由整除性质 3，立即得到 $\phi(x)|1$，即 $f(x)$ 与 $g(x)$ 互素。

　　 证明：由 $(f(x),g(x))=1$ 和定理 3 可知，有 $u(x),v(x)$ 使

上式两边乘 $h(x)$，得 因为 $f(x)|g(x)h(x)$，所以 $f(x)$ 整除等式左端，从而 $f(x)|h(x)$。

　　 证明：因为 $(f_1(x),f_2(x))=1$，由定理 3 ，存在 $u(x),v(x)$，使得

上式两边乘 $g(x)$，则 又 $f_1(x)|g(x),f_2(x)|g(x)$，则有 $q_1(x),q_2(x)$，使得 式 17 代入 式 16 ，得 所以 $f_1(x)f_2(x)|g(x)$。

---

1. ^ 吴群。矩阵分析[M].上海：同济大学出版社
2. ^ 环是一种数学结构，详见小时百科《代数学进阶》部分。