多項式最大公因式的“更相減損術”

劉興祥，王 姣，張 宇

(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)

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)。