一元多項式最大公因式的求法

1、元多項式最大公因式的求法摘要多項式理論是高等代數(shù)的重要組成部分，求最大公因式在多項式理論研究中占有顯著地位.求兩個多項式的最大公因式，一般采用因式分解法和輾轉(zhuǎn)相除法.本文還試圖從：彳將兩種方法結(jié)合起來 2矩陣的初等變換法 矩陣的斜消變換法以及數(shù)值矩陣法等不同角度給出了一元多項式的最大公因式的不同求法關(guān)鍵詞 因式分解法；輾轉(zhuǎn)相除法；斜消變換法；矩陣初等變換一引言最大公因式的概念是多項式代數(shù)的重要內(nèi)容，關(guān)于最大公因式的求法一般主要討論兩個多項式的最大公因式的求法，方法主要有因式分解法和輾轉(zhuǎn)相除法.考慮n個多項式的最大公因式時，往往也是通過兩兩多項式求最大公因式，因此求多個多項式的最大公因式需要多次

2、對兩個多項式進(jìn)行運算.為了改進(jìn)運算方法，我們給出以下的矩陣初等變換法，斜消變換法等利用多項式矩陣和數(shù)字矩陣的運算來求解最大公因式,雖然不盡完善，但也是一種很大的突破.本文將在此基礎(chǔ)之上對求最大公因式的方法進(jìn)一步作一個較全面的探討.二問題的提出在高等代數(shù)教材1中，有如下定義和定理:定義1如果多項式W(X溉是f(x)的因式，又是g(x)的因式，那么W(X)就稱為f(x )與g(x)的一個公因式.定義2設(shè)f(x ), g(x )是Px中兩個多項式.Px中多項式d(x)稱為f(x),g(x )的一個最大公因式，如果它滿足下面兩個條件:1) d(x是 f(x), g(x)的公因式;2) f(x ),g(

3、x)的公因式全是d(x)的因式.我們約定，用(f(x)g(x)來表示最高次項系數(shù)為 1的那個最大公因式.三問題的解決由定義1和定義2我們很容易得到一種求多項式的最大公因式的方法一因式分解法3.1因式分解法利用兩個(多個)多項式的標(biāo)準(zhǔn)分解式可以很快地得到它們的最大公因式.如:設(shè)多項20式f(x)與g(x)的標(biāo)準(zhǔn)分解式分別為:f(x)=ap(x)卩2&)Prmr(x); g(x) =bpj (x)p2 (x) p(x)(上式a,b分別是f(x),g(x)的首項系數(shù).p1 (x),pr(x)是兩兩不等的首項系數(shù)為1的不可約多項式， mi,mr, 0|/ nr是非負(fù)整數(shù)，則(f(x),g(x)= pk

4、1(x)pYd)pYd)這里 ki =ming,nji =1,2,r例3.1.1 證明Pn 0,(x2 +x+1,xn電一(x+1)2n卅)=1證明:(x+1)2n* =(x +1)(x2 +2x + 1)n= (x2+x+1)+xn(x+1) = (x + 1)(x2 +x + 1)n +(x + 1)xn最后一項Xn書一(X +1)xn =xn(x2 -X-1)不能被x2 +x + 1整除 故命題得證.對于因式分解法，雖然，直觀，原理簡單易懂.但當(dāng)多項式次數(shù)較高時，分解的過程往往比較困難，故此方法并不理想.沒有廣泛適用性.定理1對于Px中任意兩個多項式f(X ), g(x ),在Px中存在

5、一個最大公因式d(x),且d(x可以表成f(x), g(x )的一個組合，即有 Px中的多項式u(x), v(x )使d(X )= u(x )f(X )+ v(x g(x).證明 如果f(x ), g(x有一個為零，譬如說，g(x)=0，那么f(x)就是一個最大公因式，且f(x)=1 f x)+1 0.F面來看一般的情形.無妨設(shè)g(x)HO.按帶余除法,用g(x )除f (X ),得到商qx),余式r,(X )如果rjx0,就再用r/x )除g(x),得到商q2(x ),余式rx);又如果“(xjH 0 ,就用r2(X 除 r,(X )得出商q3 (x )余式r3(x J如此輾轉(zhuǎn)相除下去,顯然

6、,所得余式的次數(shù)不斷降低,即耳g(x)(ri(x )點(2以)因此在一有限次之后，必然有余式為零，于是我們有一串等式;f(x)=qi(x)g(x)+ ri(x), g(x)=q2(xri(x)+ rx),ri_2(x)= qi(x)ri_i(x)+ rjx),rs_3(x) = qs4(xrs_2(x)+rs_j(x).rs2(x)=qs(x)rs4(x)+rs(xrs(x)=qs4i(xys(x)+0.rs(X 肯 0的最大公因式是rs(x y根據(jù)前面的說明，rs(x辿就是rs(x )與rsj(x)的一個最大公因式；同樣的理由，逐步推上去，rs(x)就是f(x)與gx)的一個最大公因式.由上

7、面的倒數(shù)第二個等式，我們有rs(x)=rs/(x)qs(xrs4(x)再由倒數(shù)第三式，rsj(x )= rsd(x)-qs4(x代入上式可消去 3(x1得到rs(X )= (1 + qs(X 瓦_(dá)1(X )人/(X ) qs(X h J x)然后根據(jù)同樣的方法用它上面的等式逐個消去，再并項就得到這就是定理的式.證畢由最大公因式的定義不難看出，如果d1(x)d2(x 是 f(x)與g(x)的兩個最大公因式,那么一定有 d1(x)|d2(x 與 d2(x)|d1(x )，也就是 d1(x)=cd2(x), cH0.這就是說，兩個.我們知道，兩個多項式的最大公因式在可以相差一個非零的常數(shù)倍的意義下是

8、唯一確定的不全為零的多項式的最大公因式總是一個非零多項式由定理1的證明過程我們找到一種求多項式的最大公因式的方法一輾轉(zhuǎn)相除法3.2 輾轉(zhuǎn)相除法例3.2.1 求f(X盧g(x )的最大公因式:f (x)=x4 +x3 -3x2 -4x-1,g(x)= x3 + x2 -x-1.解用輾轉(zhuǎn)相除法，得1 1q2(x) 2x + 4g(x )= x3 + x2 -X -1f (x)= X4 + X3 -3x2 -4x-1X4 +x3-X2 -Xx = q1(x)33x + 22 1 X + X21 2 x21 2 x -23x123 1Yzx4 4rxA-2x2 -3x-1-2x2 -2x84亍十齊q3

9、(X)r2(x)=3 3 X4 4-x-1-x-10故(f(x)g(x)=x+1為了運算的簡化，我們可以在輾轉(zhuǎn)相除的開始或過程中用一個非零常數(shù)去乘被除式或者除式，而對計算結(jié)果無影響 .此外，在輾轉(zhuǎn)相除的過程，若遇到兩個多項式的次數(shù)相同時，可以任取一個作除式，另一個做被除式.并且為了減小多項式的系數(shù)，也可以將被除式減去除式的若干倍再做輾轉(zhuǎn)相除，不改變(f(x),g(x)的結(jié)果.2x例 3.2.2 設(shè) f(X)=1 +x +2!n2n叱,g(x)十x噲+求f(x), g(x)的最大公因式d(x).nx解：常f(x)g(x)=是d(x)的倍式 n!nxm(1m n).x而 的因式只有兩種可能：或是常

10、數(shù)C,或是n!但是 x不整除f(x)，也不整除g(x)/. d(x) =c,即 f (x)與 g(x)互素輾轉(zhuǎn)相除法具有可操作性，較因式分解法適用范圍更廣，有具體的格式進(jìn)行操作當(dāng)已知的多項式次數(shù)較高時或者多項式的個數(shù)較多時,輾轉(zhuǎn)相除次數(shù)較多顯得十分麻煩;求u(x)v(x時，輾轉(zhuǎn)相除的過程不能用一個非零的常數(shù)去乘除式和被除式，運算困難3.3因式分解法和輾轉(zhuǎn)相除法在輾轉(zhuǎn)相除法的運算中，ri(x)(1,- s)都是f(x),g(x)的最大公因式的倍式樣，只要發(fā)現(xiàn)某一 r/x)能較快的因式分解,就可用此分解式中不可約因式試除f (x), g(x)而得到最大公因式例 3.3.1r “ 、 C 17 ,

11、L 16 L 15 , c 14 , c 13f(x)=2x +5x -5x +6x +2x121110 “ 9 , “ 8 c 7 , c 6-x +x +x -10x + 10x -9x +3x+11X5 -10x4 +12X3 +6x2 -6x+6g(x)二?15 +7x14 -x12 +X11 +x10 -10x7 +x5 +4x4 +14x3-2x+4計算f(x),g(x)的最大公因式.解：由輾轉(zhuǎn)相除法得f 、C 15 丄-71412.g(x)=2x +7x -x +11 丄10”c7.5.,4.x +x -10x +x +4x +14x3 -2x+4f(x) = 2x17 +5x1

12、6 5x15 + 6x14+2x13-x12 +x11+x10- 10x9+10x8 -9x7 +3x6x2 -X + 1 = q(x)rx) -x11 +2f(x(x1)g(x(x12)寫r1(x) x11 +2是有理數(shù)域上的不可約多項式”r1(x)的因式只可能是X11 +2或常數(shù)用X11 +2試除，得X11+2不整除f(x), g(x)，所以，f(x),g(x)的最大公因式是常數(shù)，即f(X), g(x)互素.在了解了用上述格式表示輾轉(zhuǎn)相除法的過程后，我們還可以用另一種更簡單,直觀的方式來表示這種過程.3.4 矩陣法1.求兩個多項式的最大公因式令f1, f2是兩個多項式，不妨設(shè)cf cf2，

13、用f1去除f2有f尸f1g12 + r12，cr12 cf ，即(f1f2jl1g12L(f112).設(shè)A1J1g12l 可知 A 是可逆陣，再用o10112去除t1 01亠r 1 01有f1=r12g21 +r21住“2，即(f112)1 1嚴(yán)2112)設(shè) 1扁21，則 A也是可逆陣，依次做下去，由于j在絕對遞減，必有某時有(rk1 rk2)=(0rk2 )或(rk10)妨 設(shè)01 = d H 052=0(f1 f2 AA2As =(d0)(f1f2)A = (d 0)，其中A = A1A2代是可逆陣的第一列為5,口2，則有fu + f2U2 =d .又由于(f,f2 ) = (d0A，于是

14、f1, f2均可由d表示，即d是f1, f2的公因式.綜合得d是fjf?的最大公因式.例 341ft= 4x4-2x316x2+5x +9,f2 =Zx3x2-5x + 4.求 t 與 f2 的最大公因式d(x)解 廳2 V 臥，作除法 t = f2(2x )+ (- 6x2 -3x +9 ),即也f2)；x ：N6x2-3x+9 fJ再作除法f 11 f2 = (6x2 3x + 9 j + i + (x+1),3 x 3 丿(_6x2 3x +92 /L0,111 x -331= (_6x2_3x +9x+1再作除法,2-6x 3x + 9 = ( X+1 j(6x + 9 )+0,(-6

15、x2 -3x+9 _x +1 才1 0-6x-91=(0-X + 1)d(x)= X+12.求3個多項式的最大公因式f1,f2,f3是3個多項式，滸1=m i作f,吋2,吋3，用fl去除f2, f3 ,有f flgl2+12, f3=仏13 +13,即(f1 f21 f3 )0L0一 g12 一 g 131001=(f11213 ) A1 =J10L0-g 1210-g13 101.不妨設(shè)育仁=mi12cr13，再用r12去除f1和r13，有1 =12 921 中21,13=12023 中23，g 211 g 23= (211223 )A2=001L1g 210匕j 絕對遞減，必有某時(ft1

16、2r 13繼續(xù)作下去，由于rki, rk2, rk3中有一個不為零，其余全為零不妨設(shè)k1 =d H0,k2 =k3 = 0，則有(f1fsRA?人=(d 0 0)，記A=AiA2As(Ai, A2,As均可 逆則有(fif2f3人=(d 0 0 ).設(shè)A的第一列f3)=(d 0 01A*，即 f1, f2,f3為 u1,u2,u3,則 f1 u1 + f2u f3u d .又寫(f1均可由d表示，即d是fj, f2, f3的公因式.故d是最大公因式.例 3.4.2f1 =4x4 2x3 -16x2 +5x+9, f2 = 2x3 x2 5x + 4, 3 =x2 -2x + 1.求fj, f2

17、, f3的最大公因式.解區(qū)最小，用f3去除ft, f?，有f1 = f3 (4x2+ 6x 一8 ) +(17x +17 , f2=f3 (2x +3)+(-x +1 ,即f1f2I1)02L_4x -6x +801-2x -3= (-17 x +17-x+1 f3 )_x +1J最小，再作除法,-17x+17 =(-x+ 1117)+0, f3=(一 X +1 (- X +1)+ 0.-x +1 f31)-17I 0j = (0-x+10J=-x+1是最大公因式.3.求n個多項式的最大公因式fi, f2 - fn是n個多項式， f,-min滸1，點f2；旨n,用f1去除f2,fn,有r1n,

18、f2 = f1 g12 +12, f3 = f1g13 +13,fn =彳心仆 +(fif210g 12110L0-g121g 1n0g 1n0(必是可逆陣)= (firi2r1nL0不妨設(shè)cr12=min(f1,打13,jsrm )，再用s去除彳“彳,心有f 1=12 g21 +21*13 =12 g23 +23Hn =r12g2n +r2n(f 1 r12r1ng21-g2n= (21r12r2n設(shè)a2 =一 g21一 g2n(必是可逆陣).繼續(xù)下去，由于 QrJ絕對遞減，必有某時(f1 f2(f1 f2(rn，An)中只有個不為零其余全為零.不妨設(shè)ri1=dH0 ,則fn PAs =(d

19、 0 0).設(shè) A= AA2As是可逆陣，fn A = (d 0 0)，設(shè)A的第一列為U1,U2,Un ，有f1U1 + f2U2 + fnUn =d，且寫(仇f?fn )=(d 0 0A，f1, f2,，fn均可由d表示，即d是f1, f2,，fn的公因式.故d是最大公因式.矩陣法在輾轉(zhuǎn)相除法的基礎(chǔ)上，結(jié)合多項式最大公因式的定義與矩陣的運算性質(zhì),不緊可以求兩個多項式的最大公因式還可以求得多個多項式的最大公因式并同時求得d(x)關(guān)于fjxli =1,2，,n )的線性組合.雖采用的是矩陣形式，但仍需要兩兩多項式作除法,隨著多項式的個數(shù)增加計算量大大增加，計算過程比較復(fù)雜3.5矩陣的初等行(列)

20、變換法定理2設(shè)A = (f1(X 1 f2(x )，fn(X瓜n是Px上的非零陣,d(x) =(f1(x1f2(x)，fn(x), In 是 n階單位矩陣，B =(d(x)0，0)浦，則矩陣(A;經(jīng)過一系列初等列變換可化為(叮，而R(x)的第一列元素就是lR(x)丿Ui(x)(i =1,2,n )，使得f1(xU1(X)+ f2(xU2(X)中+ fn(xUn(X)=d(X)成立.例 3.5.1對于整系數(shù)多項式f (x)=3x2 +5X-2; f2(x)=x3 +x2 -x + 2;f3(x )=2x +3x3 中 X2 中 6x.求它們的最大公因式 d(x)f20f3、0對其進(jìn)行如下的的列初

21、等變換:f1f2f3、1I1f22 、2x +3X-210101_疋士吐T10001001-2x-1001丿001 丿3x + 21丿2 +2xi311T；2 +2xf22 、2x2 +3x -2f10021刊2卩護(hù)2x +112x -1-101z（ 00X +21、12x +1-11 X2x2 +x +1x+2x-1-26x-3-2x +1-6x2 -X +1-X-1-2x2 -5X-23x1x+2其中,R（x）= 6L 3X +36x+33丿-x-12-2x 5x-2x+26x+3-X-1-2x2 -5X-2-2x + 1 6x2 - x + 1x+23x-1 丿-2x +112-6x -

22、x + 13x1d（X ） = x + 2,d(x)是唯注：進(jìn)行初等變換的目的是要把C的第一行變成(d(x) 0 0形式，在作初等列變換過程中，系數(shù)保持是整數(shù)，在這個原則下可以隨意地作初等列變換，得到的一的但由于作法不同，得到的R(x )的第一列元素Ui(X 1= 1,2,n )可能不同，故線性表示不唯一，但都能使仇（X U1（X ）+ f2（X U2（x）+ f3（xU3（x）=d（x）矩陣的初等變換法通過直接構(gòu)造矩陣，利用多項式矩陣的初等變換一舉求得最大公因式d(x及其線性表達(dá)式，具有較廣的使用范圍且運算過程較靈活，避免了多項式之間繁瑣的除法運算.但由于構(gòu)造的是多項式矩陣，故在運算過程中仍

23、是多項式的運算，有一定的難3. 6矩陣的斜消變換基于矩陣的初等行,列變換法，我們思考是否存在一種運算過程來避免多項式之間繁瑣的除法運算.定義3 設(shè)fi (x)= ai1Xn +ai2Xn屮+ ai,nx + 為，(i =1,2，,m)為 m個多項式(至少有一個多項式不為零)，A = (aij)為mxn階矩陣，a為與多項式f/x)，( i=1,2,，m)相對應(yīng)的矩陣.若A的第i行從左向右第一個不為零的元素為ai,4,第j行的第一列元素 aj1不為零(iHj),則稱將第i行的n-s個元素：ai,s卄ai,sH2,，ain乘以c斜加到第j行元素:aj1,aj2 ,aj,n上的變換為第i行到第j行的左

24、斜消變換記為 LS(C);若A的第i行從右向左第一個不為零的元素為 ais , 1 S 0-1-P10-1-PJ1廠-112山（二） ?02222亠)T000丿000丿00丿-1-P11、00T0000丿0x0丿所以,(f(x),g(x),h(x) =x+1要及時我們約定，用左斜消變換化簡矩陣時，若所得矩陣的前若干列元素全為零時,消去這些列再做變換；用右斜消變換化簡矩陣時，若所得矩陣的后若干列元素全為零時，要 及時消去這些列再做變換.這樣可以達(dá)到簡化矩陣的目的在用斜消變換化簡矩陣時，我們會發(fā)現(xiàn)，求某些多項式的最大公因式時，需要選擇其適用的是左斜消變換還是右斜消變換.并且左右斜消變換是不能同時使

25、用的，這就給我們解決某些問題時帶來了局限性3. 7數(shù)值矩陣法若用矩陣A = iananIbnbn_iaia0b,b。丿I表示多項式： f（X）= anXn+anxn中+a0g(x) =bnX J bnx+b0的待求最大公因式.則對A施行初等行變換，不改變兩個多項式的最大公因式./an an 43130an 31a。.bnbn4b1b0丿.0bzb1b0丿當(dāng)a。H 0時，,即它們表示的兩個多項式的待求最大公因式相同其一般利用以上結(jié)論，就可以利用矩陣的初等行變換求出一元多項式組的最大公因式, 步驟為: 將系數(shù)矩陣A利用初等行變換化為階梯矩陣B 考察矩陣B，若出現(xiàn)元素都是 0的行，則去掉該行；若某行

26、變?yōu)椋? 0 kik H0時，多項式的最大公因式為 1,計算終止；若出現(xiàn)每一行的列數(shù)最大的非零元素不在同一列時， 則施行右對齊；若每一行的列數(shù)最大的非零元素在同一列時,施行左對齊；將 B變成非階梯矩陣，然后，以非零元素最少的行將其再化成階梯矩陣 反復(fù)循環(huán)上述步驟，直到 A變?yōu)?x( n +1型矩陣，則對應(yīng)的多項式即是的最大例 3.7.1設(shè) f(X)= X3 -3x2 -2x +6, g(x) = X3 +x2 - 2x-2,( f (x), g(x) =?解：對矩陣A=白-3 -2-26 I-2丿施行初等行變換及替換:At j1-3-26、一8廠0q0-2 0、TTP10 一2丿故,-3-26

27、 、0-2丿-2)0-2；(f(x),g(x) =(x2 2,0)223.7.2f(X)=x4 -4x3 +2x2 +4x -32-4x +x + 6h(x) =x-2x2x+2 求(f(x),g(x),h(x)-424-3 1-424-3、解A=01-416T0141601-2-12丿02-2-4丿z/1-424-311-2001-1-2001-41 60T1-4160T0-33602-2-4001-424-3001-2-3丿X丿001-1-2、廣001-1-2 1M00-336T000-1-10X01-2-3丿,00000丿3:00001-10所以,-2-10-2、00丿 -2、 -1 0丿(f(x),g(x),h(x) =x+10-10-2-10100丿數(shù)值矩陣法根據(jù)多項式與其系數(shù)間的一一對應(yīng)關(guān)系，構(gòu)造多項式組的系數(shù)矩陣A，再由多項式最大公因式的性質(zhì)導(dǎo)出一種單純運用數(shù)字矩陣（系數(shù)矩陣A