多项式最大公因式的“更相减损术”

刘兴祥，王 姣，张 宇

(1.延安大学数学与计算机科学学院，陕西延安716000；2.西安建筑科技大学信息与控制工程学院，陕西西安710000；3.西北农林科技大学理学院，陕西咸阳712000)

关于求整系数项多项式最大公因式，大多数教材均介绍了“辗转相除法”[1]，国际上将其称为欧几里得算法，是一种古老的算法[2]，出现在欧几里得的《几何原本》[3]中。而在我国，更相减损这种古老的数学思想[4-9]在实际的操作过程中却被仅仅局限于最终获得的等数。本文将对更相减损术进行引申，根据其原理与矩阵行初等变换原理存在的一定相似性，将其扩充至求两个整系数多项式的最大公因式，进而将“更相减损术”从两个整系数多形式推广至多个整系数多项式。

1 “更相减损术”计算最大公因式

在九章算术中“更相减损术”是一个及其重要的基本算法，其原理为：其所以相减者，皆等数之重叠，故以等数约之。不仅适用于化简分数，同样可用于多项式来求最大公因式。

2 计算两个整系数多项式的最大公因式

矩阵的行(列)初等变换指的是对一个矩阵施行的下列变换:

(1)交换矩阵的两行(列)；

(2)用一个不等于零的数乘矩阵得某一行(列)，即用一个不为零的数乘矩阵得某一行(列)的每一个元素；

(3)用某一数乘矩阵得某一行(列)后加到另一行(列)，即用某一数乘矩阵的某一行(列)的每一元素后加到另一行(列)的对应元素上[10]。

“更相减损术”其步骤如下:

令F是数域，求F[x]的多项式

f(x)=a0xn+a1xn-1+…+an-1x+an，

g(x)=b0xm+b1xm-1+…+bm-1x+bm，

ai,bj∈F(i=0，1，2，…，n；j=0，1，2，…，m)，求(f(x),g(x))。

我们首先引进多项式形成的矩阵，把两个多项式写成矩阵，将其按照矩阵初等变换中的第二和第三性质进行变换。具体的步骤如下：

第一步：

(1)分别给f(x)乘以v，使得vxn=xm，此时

vf(x)=va0xn+va1xn-1+…+van-1x+van,

g(x)=b0xm+b1xm-1+…x+bm-1x+bm，

使得vf(x)和g(x)中的最高次数相同。

(2)给g(x)乘以w，使得a0=wb0，此时，

wg(x)=wb0xm+wb1xm-1+

…+wbm-1x+wbmf(x)=

a0xn+a1xn-1+…+an-xx+an，

通过两次计算会产生va0xn=wb0xm，

使得r(x)=vf(x)-wg(x)(则可以将f(x)中得anxn项去掉)。

第二步：此时

r(x)=vf(x)-wg(x)=

(a1-wb1)xm-1+(a2-wb2)xm-2+

…+(van-wbn)，

给r(x)和g(x)分别乘以v1和w1，使得

v1(a1-wb1)xm-1=w1b0xm，

则r1(x)=w1g(x)-v1r(x)(可以将g(x)中得b0xm项去掉)。

第三步：依次循环一二步进行降次数，直到rq(x)和rq-1(x)对应成比例，则

(f(x),g(x))=rq(x)。

注：vi，wj∈F(i=0，1，2，…，j=0，1，2，…)，vi,wj根据f(x)和g(x)得最高次项的系数和次数选取，要使的其系数和次数对应相等。所以vi,wj可以取常数也可以取含x的一次或多次项。

例1 令F是数域，求F[x]的多项式

f(x)=x4-2x3-4x2+4x-3，

g(x)=2x3-5x2-4x+3，

求(g(x),f(x))。

解按照更相减损法计算。

即(f(x),g(x))=x-3。

定理1f(x)=a0xn+a1xn-1+…+an-1x+an,

g(x)=b0xm+b1xm-1+…+bm-1x+bm，

构造矩阵为

经过行初等变化为

(f(x),g(x))=(f1(x),g1(x))，且

f1(x)=u1(x)f(x)+v1(x)g(x),

g1(x)=s1(x)f(x)+t1(x)g(x)。

定理2[11]

f(x)=a0xn+a1xn-1+…+an-1x+an,

g(x)=b0xm+b1xm-1+…+bm-1x+bm，

构造矩阵为

经过行初等变换得到

满足条件d(x)|f(x)且d(x)|g(x)。

则可知

(1)d(x)为f(x)，g(x)的最大公因式；

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

证明结论(2)是定理1的直接结果。

若d(x)|f(x)，d(x)|g(x)且满足结论(2)，那么d(x)是f(x)，g(x)的最大公因式。则只需要证明d(x)|f(x)，d(x)|g(x)。

若f(x)=g(x)=0，则d(x)=0，命题成立。

若g(x)=0，f(x)≠0，则d(x)=f(x)，命题成立。

若g(x)≠0，f(x)≠0，则可以设∂0f(x)≤∂0g(x)，B(x)可以通过若干次初等变换得到，假设第一次初等变换关系式f1(x)=g(x)+φ1(x)f(x)，即A(x)变为

设∂0f1(x)<∂0f(x)(若干次变换之后得到)，继续上述步骤，设经过r次，直至fr(x)=0，相关的变换关系式是

f2(x)=f(x)+φ2(x)f1(x)，

f3(x)=f1(x)+φ3(x)f2(x)，

……，

fr-1(x)=fr-3(x)+φr-1(x)fr-2(x)

(1)

0=fr-2(x)+φr(x)fr-1(x)

(2)

从上述(1)式可知fr-1(x)=d(x)，又从(2)式可知道d(x)|fr-2(x)，(1)式可知d(x)|fr-3(x)，依次向上递推知道d(x)|f(x)，d(x)|g(x)，从而d(x)是f(x)，g(x)的最大公因式，证明完毕。

同样的在辗转相除法中也给出了其对应的求法，在此处就不再进行叙述。值得注意的是在陈占铁[12，13]所著的新辗转相除法一文中，给出了新的求u,v的方法，他的推理特别是反推求u,v上与旧方法有很大不同，程序较为简单，计算容易。

3计算三个或者多个整系数多项式的最大公因式

“更相减损术”不仅可以求两者之间的最大公因式，还可以求三者，甚者更多。下面给出三个或者多个整系数多项式之间的最大公因式的解法:求三者等也，先求任两者等也。余其一，与两者等也，有一等数，此等数，即为三者等也。若有多者，似其三者求也。

依据令F是数域，求F[x]的多项式

f(x)=a0xn+a1xn-1+…+an-1x+an，

g(x)=b0xm+b1xm-1+…+bm-1x+bm，

h(x)=c0xq+c1xq-1+…+cq-1x+cq，

ai,bj,cs∈F(i=0，1，…，n；j=0，1，…，m；s=0，1，…，q)，

求这三个多项式的最大公因式。

第一步：先按照更相减损法求出其中任意两者的最大公因式，

第二步：再求第一步获得的最大公因式和余下的多项式之间的最大公因式。

例2 多项式f(x)，g(x)和h(x)分别为

f(x)=x4-9x3+27x2-31x+12，

g(x)=x4-4x3-x2+16x-12，

h(x)=x3-5x2-2x+24，

求f(x),g(x),h(x)的最大公因式。

解按照更相减损法计算。

第一步：先求(f(x),h(x))。

即(f(x),h(x))=x2-7x+12。

第二步：再求((f(x),h(x)),g(x))。

即(f(x),h(x),g(x))=x-3。

综上所述：f(x),g(x),h(x)的最大公因式为((f(x),h(x)),g(x))=x-3。

上面对于两个多项式求u(x),v(x)的方法也可以推广到多个多项式求u(x),v(x)上去。

定理3 构造矩阵

经过行初等变换

d(x)=u1(x)f1(x)+u2(x)f2(x)+…+

un(x)fn(x)。