多項(xiàng)式最大公因式的“更相減損術(shù)”

劉興祥，王 姣，張 宇

(1.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西延安716000；2.西安建筑科技大學(xué)信息與控制工程學(xué)院，陜西西安710000；3.西北農(nóng)林科技大學(xué)理學(xué)院，陜西咸陽(yáng)712000)

關(guān)于求整系數(shù)項(xiàng)多項(xiàng)式最大公因式，大多數(shù)教材均介紹了“輾轉(zhuǎn)相除法”[1]，國(guó)際上將其稱為歐幾里得算法，是一種古老的算法[2]，出現(xiàn)在歐幾里得的《幾何原本》[3]中。而在我國(guó)，更相減損這種古老的數(shù)學(xué)思想[4-9]在實(shí)際的操作過(guò)程中卻被僅僅局限于最終獲得的等數(shù)。本文將對(duì)更相減損術(shù)進(jìn)行引申，根據(jù)其原理與矩陣行初等變換原理存在的一定相似性，將其擴(kuò)充至求兩個(gè)整系數(shù)多項(xiàng)式的最大公因式，進(jìn)而將“更相減損術(shù)”從兩個(gè)整系數(shù)多形式推廣至多個(gè)整系數(shù)多項(xiàng)式。

1 “更相減損術(shù)”計(jì)算最大公因式

在九章算術(shù)中“更相減損術(shù)”是一個(gè)及其重要的基本算法，其原理為：其所以相減者，皆等數(shù)之重疊，故以等數(shù)約之。不僅適用于化簡(jiǎn)分?jǐn)?shù)，同樣可用于多項(xiàng)式來(lái)求最大公因式。

2 計(jì)算兩個(gè)整系數(shù)多項(xiàng)式的最大公因式

矩陣的行(列)初等變換指的是對(duì)一個(gè)矩陣施行的下列變換:

(1)交換矩陣的兩行(列)；

(2)用一個(gè)不等于零的數(shù)乘矩陣得某一行(列)，即用一個(gè)不為零的數(shù)乘矩陣得某一行(列)的每一個(gè)元素；

(3)用某一數(shù)乘矩陣得某一行(列)后加到另一行(列)，即用某一數(shù)乘矩陣的某一行(列)的每一元素后加到另一行(列)的對(duì)應(yīng)元素上[10]。

“更相減損術(shù)”其步驟如下:

令F是數(shù)域，求F[x]的多項(xiàng)式

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

我們首先引進(jìn)多項(xiàng)式形成的矩陣，把兩個(gè)多項(xiàng)式寫成矩陣，將其按照矩陣初等變換中的第二和第三性質(zhì)進(jìn)行變換。具體的步驟如下：

第一步：

(1)分別給f(x)乘以v，使得vxn=xm，此時(shí)

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

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

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

(2)給g(x)乘以w，使得a0=wb0，此時(shí)，

wg(x)=wb0xm+wb1xm-1+

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

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

通過(guò)兩次計(jì)算會(huì)產(chǎn)生va0xn=wb0xm，

使得r(x)=vf(x)-wg(x)(則可以將f(x)中得anxn項(xiàng)去掉)。

第二步：此時(shí)

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項(xiàng)去掉)。

第三步：依次循環(huán)一二步進(jìn)行降次數(shù)，直到rq(x)和rq-1(x)對(duì)應(yīng)成比例，則

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

注：vi，wj∈F(i=0，1，2，…，j=0，1，2，…)，vi,wj根據(jù)f(x)和g(x)得最高次項(xiàng)的系數(shù)和次數(shù)選取，要使的其系數(shù)和次數(shù)對(duì)應(yīng)相等。所以vi,wj可以取常數(shù)也可以取含x的一次或多次項(xiàng)。

例1 令F是數(shù)域，求F[x]的多項(xiàng)式

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

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

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

解按照更相減損法計(jì)算。

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

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

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

構(gòu)造矩陣為

經(jīng)過(guò)行初等變化為

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

構(gòu)造矩陣為

經(jīng)過(guò)行初等變換得到

滿足條件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)。

證明結(jié)論(2)是定理1的直接結(jié)果。

若d(x)|f(x)，d(x)|g(x)且滿足結(jié)論(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，則可以設(shè)?0f(x)≤?0g(x)，B(x)可以通過(guò)若干次初等變換得到，假設(shè)第一次初等變換關(guān)系式f1(x)=g(x)+φ1(x)f(x)，即A(x)變?yōu)?/p>

設(shè)?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)的最大公因式，證明完畢。

同樣的在輾轉(zhuǎn)相除法中也給出了其對(duì)應(yīng)的求法，在此處就不再進(jìn)行敘述。值得注意的是在陳占鐵[12，13]所著的新輾轉(zhuǎn)相除法一文中，給出了新的求u,v的方法，他的推理特別是反推求u,v上與舊方法有很大不同，程序較為簡(jiǎn)單，計(jì)算容易。

3計(jì)算三個(gè)或者多個(gè)整系數(shù)多項(xiàng)式的最大公因式

“更相減損術(shù)”不僅可以求兩者之間的最大公因式，還可以求三者，甚者更多。下面給出三個(gè)或者多個(gè)整系數(shù)多項(xiàng)式之間的最大公因式的解法:求三者等也，先求任兩者等也。余其一，與兩者等也，有一等數(shù)，此等數(shù)，即為三者等也。若有多者，似其三者求也。

依據(jù)令F是數(shù)域，求F[x]的多項(xiàng)式

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

求這三個(gè)多項(xiàng)式的最大公因式。

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

第二步：再求第一步獲得的最大公因式和余下的多項(xiàng)式之間的最大公因式。

例2 多項(xiàng)式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)的最大公因式。

解按照更相減損法計(jì)算。

第一步：先求(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。

上面對(duì)于兩個(gè)多項(xiàng)式求u(x),v(x)的方法也可以推廣到多個(gè)多項(xiàng)式求u(x),v(x)上去。

定理3 構(gòu)造矩陣

經(jīng)過(guò)行初等變換

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

un(x)fn(x)。