|
|
本帖最后由 zhcosin 于 2017-6-21 17:53 编辑 最大公因数与辗转相除法
定义 如果$d(x) \mid f(x)$且$d(x) \mid g(x)$，则称$d(x)$是$f(x)$与$g(x)$的一个公因式.
显然常数因子是任何两个多项式的公因式，因而公因式是存在的。
定义 多项式$f(x)$与$g(x)$的诸公因式中，次数最高的那一个称为这两个多项式的最大公因式.
这个定义的问题是，有没有可能同时存在多个次数都最高的公因式(只相差一个常数因子的视为同一个)，也就是最大公因式的唯一性问题。
而流行的定义是:
定义 设$d(x)$是$f(x)$与$g(x)$的一个公因式，如果$f(x)$与$g(x)$的所有公因式都是$d(x)$的因式，则称$d(x)$是$f(x)$与$g(x)$的最大公因式.
这个定义也有个问题，在这诸公因式中，次数最高的那个，是否能被别的所有公因式都整除呢，所以无论采用哪一种定义，都有些问题要留待对最大公因式有一定程度的讨论后才能解决，这就是最大公因式的性质定理:
最大公因式性质定理 设$d(x)$是$f(x)$与$g(x)$的最大公因式，则存在多项式$u(x)$和$v(x)$，使得
\[ d(x) = u(x)f(x) + v(x)g(x) \]
为证明这个定理，先提出如下引理
引理 如果有等式
\[ f(x)=q(x)g(x)+r(x) \]
则$f(x)$与$g(x)$的公因式，也必然是$g(x)$与$r(x)$的公因式.
由整除性质，引理是显然的。
现在证明最大公因式的性质定理:
证明 根据带余除法，存在多项式$q_1(x)$及$r_1(x)$(次数低于$g(x)$或者是零多项式)，使
\[ f(x)=q_1(x)g(x)+r_1(x) \]
如果$r_1(x)$不是零多项式，则再继续拿$g(x)$除以$r_1(x)$，得出
\[ g(x) = q_2r_1(x)+r_2(x) \]
如此反复下去，因为每进行一次，$r_i(x)$的次数至少减少一，因此必然在有限步之后，$r_i(x)$成为零次多项式即为常数，再进行一次之后，$r_i(x)$便成为零多项式，把这过程写成等式序列，并记$r_{-1}(x)=f(x)$,$r_0(x)=g(x)$，便是
\begin{eqnarray*}
r_{-1}(x) & = & q_1(x)r_0(x)+r_1(x) \\
r_0(x) & = & q_2(x)r_1(x)+r_2(x) \\
\cdots \\
r_{k-1}(x) & = & q_{k+1}(x)r_k(x)+r_{k+1}(x) \\
\cdots \\
r_{s-2}(x) & = & q_s(x)r_{s-1}(x) + r_s(x) \\
r_{s-1}(x) & = & q_{s+1}(x)r_s(x) + 0
\end{eqnarray*}
按照上述引理，$f(x)$与$g(x)$的公因式，必然也是$g(x)$与$r_1(x)$的公因式，也就必然是$r_1(x)$和$r_2(x)$的公因式，依次推下去，最后必然也是$r_s(x)$与0的公因式，从而就必然是$r_s(x)$的因式，于是$r_s(x)$本身便是最大公因式（无论按照前面的两种定义的那一种）。
从上面倒数第二个等式可以看出，$r_s(x)$可以用$r_{s-1}(x)$与$r_{s-2}(x)$表示成各自与某个多项式相乘后再相加的形式，而$r_{s-1}(x)$又可以用$r_{s-2}(x)$和$r_{s-3}(x)$用相同的形式表示出来，依次倒着推回去，最后$r_s(x)$便必定可以用$f(x)$与$g(x)$各自与某个多项式相乘后相加的形式表示出来，当然这也可以用数学归纳法的形式进行严格叙述，略去。
定理证明过程中的这个反复做带余除法的过程称为辗转相除法。
从定理证明过程中还可以看出，两个多项式的公因式，都是它俩最大公因式的因式，从而最大公因式在不考虑常数因式的意义下是唯一的。
要说明的是，定理中的$u(x)$及$v(x)$不是唯一的，这从下式中可以看出
\[ d(x) = (u(x)+h(x)g(x))f(x)+(v(x)-h(x)f(x))g(x) \]
即如果$u(x)$、$v(x)$符合定理，则$u(x)+h(x)g(x)$、$v(x)-h(x)f(x)$也符合定理，其中$h(x)$是任意多项式。
但是要强调的是，只有最大公因式才能表示成这种形式，其它公因式不具有这种表示，这就是下面的定理
定理 设$d(x)$是$f(x)$和$g(x)$的一个公因式，如果存在多项式$u(x)$和$v(x)$使得$d(x)=u(x)f(x)+v(x)g(x)$，则$d(x)$必然是最大公因式。
证明 显然根据那等式，$f(x)$与$g(x)$的任一公因式也能够整除$d(x)$，所以$d(x)$是最大公因式。
定义 如果两个多项式的最大公因式为1，即$(f(x),g(x))=1$，则称这两个多项式 \emph{互素}.
定理 两个多项式$f(x)$与$g(x)$互素的充分必要条件是，存在多项式$u(x)$和$v(x)$使得$u(x)f(x)+v(x)g(x)=1$.
证明 如果有这等式，则对于$f(x)$与$g(x)$的最大公因式$d(x)$，必然有$d(x) \mid 1$，所以两个多项式互素，充分性得证，而必要性是显然的。
定理 如果$(f(x),g(x))=1$，且$f(x) \mid g(x)h(x)$，则$f(x) \mid h(x)$.
证明 由互素，存在两个多项式$u(x)$、$v(x)$使得$u(x)f(x)+v(x)g(x)=1$，两边同乘$h(x)$得
\[ u(x)f(x)h(x) + v(x)g(x)h(x) = h(x) \]
显然$f(x)$能够整除等式左边的两项，因而也能整除右边，得证。
推论 如果$(f(x),g(x)=1)$，且$f(x) \mid h(x)$，$g(x) \mid h(x)$，则$f(x)g(x) \mid h(x)$.
证明 设$h(x)=f(x)r(x)$，则$g(x) \mid f(x)r(x)$，按前述定理，这时必有$g(x) \mid r(x)$，于是$f(x)g(x) \mid f(x)r(x) = h(x)$.
另证 由条件，存在多项式$u(x)$和$v(x)$使$u(x)f(x)+v(x)g(x)=1$，又设$h(x)=f(x)f_1(x)$，在前等式两边同乘$f_1(x)$可得$u(x)f(x)f_1(x)+v(x)g(x)f_1(x)=f_1(x)$，即$u(x)h(x)+v(x)g(x)f_1(x)=f_1(x)$，显然$g(x)$能整除等式的左边，因而也能整除右边，即$g(x) \mid f_1(x)$，从而$f(x)g(x) \mid f(x)f_1(x) = h(x)$.
最大公因式可以推广到多个多项式的情形。
定义 如果$d(x)$是一组多项式$f_i(x)(i=1,2,\ldots,n)$的公因式，并且这组多项式的任一公因式都是$d(x)$的因式，则称$d(x)$是这组多项式的公因式，也记为$d(x)=(f_1(x),f_2(x),\ldots,f_n(x))$.
定理 对一组多项式$f_i(x)(i=1,2,\ldots,n)$，定义递推序列$d_1(x)=f_1(x)$,$d_k(x)=(d_{k-1}(x), f_k(x))$，则$d_n$便是这组多项式的最大公因式。
依据这定理，最大公因式可以逐次求，先求出$f_1(x)$与$f_2(x)$的最大公因式$d_2(x)$，再求$d_2(x)$与$f_3(x)$的最大公因式，逐次下去，最后求得$d_{n-1}(x)$与$f_n(x)$的最大公因式$d_n(x)$就是这一组多项式的最大公因式。
证明 记$r_k(x)=(f_1(x),f_2(x),\ldots,f_k(x))$，易知$d_k(x) \mid f_i(x)(i=1,2,\ldots,k)$，从而$d_k(x) \mid r_k(x)$，另一方面，$r_k(x)$作为$f_1(x),f_2(x),\ldots,f_{k-1}(x)$的一个公因式，也必然是$d_{k-1}(x)$的因式，所以$r_k(x) \mid d_{k-1}(x)$，又$r_k(x) \mid f_k(x)$，所以$r_k(x) \mid d_k(x)$，因此$d_k(x)=r_k(x)(i=1,2,\ldots,n)$（不计常数因子）。
同样有性质定理
定理 设一组多项式$f_i(x)(i=1,2,\ldots,n)$的最大公因式是$d(x)$，则存在多项式$u_i(x)(i=1,2,\ldots,n)$使得
\[ d(x) = \sum_{i=1}^n u_i(x)f_i(x) \]
证明 对多项式的个数使用数学归纳法，$n=2$时显然成立，假若对于$n-1$个多项式也成立，则对于$n$个多项式的情形，由前述定理，$d_n(x)=(d_{n-1}(x), f_n(x))$，因而存在多项式$p(x)$和$u_n(x)$使得
\[ d_n(x) = p(x)d_{n-1}(x) + u_n(x)f_n(x) \]
而根据归纳假设，存在$p_i(x)(i=1,2,\ldots,n-1)$，使得
\[ d_{n-1}(x) = \sum_{i=1}^{n-1}p_i(x)f_i(x) \]
代入前式即得结论。
同样的，有多个项式互素的定义
定义 如果一组多项式的最大公因式是1，则称它们\emph{互素}。
一组多项式互素与它们两两互素是不同的，两两互素是更强的约束。
定理 一组多项式$f_i(x)(i=1,2,\ldots,n)$互素的充分必要条件是存在一组多项式$u_i(x)(i=1,2,\ldots,n)$，使得
\[ \sum_{i=1}^n u_i(x)f_i(x) = 1 \]
证明略。 |
|
