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

1、元多项式最大公因式的求法摘要 多项式理论是高等代数的重要组成部分， 求最大公因式在多项式理论研究中占有 显著地位 . 求两个多项式的最大公因式，一般采用因式分解法和辗转相除法 . 本文还试图 从： 1 将两种方法结合起来 2 矩阵的初等变换法 3 矩阵的斜消变换法以及数值矩阵法 等不同角度给出了一元多项式的最大公因式的不同求法 .关键词 因式分解法；辗转相除法；斜消变换法；矩阵初等变换一 引言最大公因式的概念是多项式代数的重要内容， 关于最大公因式的求法一般主要讨论两个 多项式的最大公因式的求法， 方法主要有因式分解法和辗转相除法 考虑 n 个多项式的最大 公因式时 ，往往也是通过两两多项式求

2、最大公因式， 因此求多个多项式的最大公因式需要多 次对两个多项式进行运算为了改进运算方法, 我们给出以下的矩阵初等变换法，斜消变换法等利用多项式矩阵和数字矩阵的运算来求解最大公因式， 虽然不尽完善， 但也是一种很大 的突破本文将在此基础之上对求最大公因式的方法进一步作一个较全面的探讨二 问题的提出在高等代数教材 1 中，有如下定义和定理：定义 1 如果多项式 x 既是 f x 的因式， 又是 g x 的因式， 那么 x 就称为 f x 与 g x 的一个公因式 .定义 2 设 f x ，g x 是 Px 中两个多项式 . Px 中多项式 d x 称为 f x ，g x 的 一个最大公因式，如果

3、它满足下面两个条件：1) d x 是 f x ， g x 的公因式；2) f x ， g x 的公因式全是 d x 的因式 .我们约定，用 f x ,g x 来表示最高次项系数为 1 的那个最大公因式 .三 问题的解决由定义 1 和定义 2 我们很容易得到一种求多项式的最大公因式的方法因式分解法 因式分解法利用两个(多个)多项式的标准分解式可以很快地得到它们的最大公因式 . 如：设多项 式 f (x) 与 g(x) 的标准分解式分别为：f(x) ap1m1(x)p2m2(x)pr mr (x); g(x) bp1n1(x)p2n2(x)prnr(x)(上式a,b分别是f(x),g(x)的首项系

4、数 p1 (x), pr(x)是两两不等的首项系数为1 的不可约多项式， m1 , mr ,n1, nr 是非负整数，则k1k2kr(f(x),g(x) Pi (x)p2 (x)Pr (x)这里 ki min ( g, nj,i 1,2, ,r例 证明2n 22n 1n 0,(x x 1,x (x 1)1证明：(x 1)2n 1 (x 1)(x2 2x 1)n(x2x 1) xn(x 1) (x 1)(x2 x 1)n(x 1)xn最后一项xn 2 (x 1)xnxn(x2 x 1)不能被x2 x 1整除故命题得证 .对于因式分解法，虽然，直观，原理简单易懂 . 但当多项式次数较高时，分解的过

5、程往往比较困难，故此方法并不理想.没有广泛适用性.定理1对于Px中任意两个多项式f x , g x，在Px中存在一个最大公因式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.下面来看一般的情形 . 无妨设 g x 0. 按带余除法 , 用 g x 除 f x ,得到商 q1 x , 余 式 r1 x ; 如果 r1 x 0 , 就再用 r1 x 除 g x , 得

6、到商 q2 x , 余式 r2 x ; 又如果 r2 x 0 , 就用 r2 x 除 r1 x , 得出商 q3 x ,余式 r3 x ;如此辗转相除下去 ,显然 ,所得余式的次数不断 降低,即g xr1 x r 2 x因此在一有限次之后，必然有余式为零，于是我们有一串等式；f x q1 x g x r1 x ，g x q 2 x r1 x r2 x ，ri 2 xqi x r i 1 x ri xrs 3 xqs 1 x rs 2 xrs 1 xrs 2 xqs x r s 1 xr s xrs 1 x q s 1 x rs x 0 .rs x 与 0 的最大公因式是 rs x . 根据前面

7、的说明， rs x 也就是 rs x 与 rs 1 x 的一个 最大公因式；同样的理由，逐步推上去，rs x 就是 f x 与 g x 的一个最大公因式 .由上面的倒数第二个等式，我们有r s x rs 2 x q s x r s 1 x .x.再由倒数第三式， rs 1 x rs 3 x qs1 x rs 2 x ,代入上式可消去 rs 1 x ,得到rs x 1 q s x q s 1 x r s 2 x qs x r s 3然后根据同样的方法用它上面的等式逐个消去，再并项就得到这就是定理的式 证毕由最大公因式的定义不难看出，如果d1 x ,d2 x是f x与g x的两个最大公因式，那么一

8、定有di x | d2 x与d2 x | di x，也就是di x cd2 x ， c 0.这就是说，两个 多项式的最大公因式在可以相差一个非零的常数倍的意义下是唯一确定的.我们知道，两个不全为零的多项式的最大公因式总是一个非零多项式由定理1的证明过程我们找到一种求多项式的最大公因式的方法一辗转相除法辗转相除法例求f x与g x的最大公因式：43小2鼻，32/f x x x 3x 4x 1,g x x x x1.解用辗转相除法，得q2 x1 -x13g x x2x x1r4f x x3 x3x24x 124332 1x432xq1 xxxxxxx2212313x 12xx2r1 x2x2841

9、-x-q3 x123233x-x42x2x2433x 1r2 xx44x 10f x ,g x x 1为了运算的简化，我们可以在辗转相除的开始或过程中用一个非零常数去乘被除式 或者除式，而对计算结果无影响 此外，在辗转相除的过程，若遇到两个多项式的次数相同 时，可以任取一个作除式，另一个做被除式并且为了减小多项式的系数，也可以将被除式减去除式的若干倍再做辗转相除，不改变 (f (x), g (x)的结果.x2例设f(x) 1 xnx,g(x) n!2x2!n 1(n 1)!求f(x),g(x)的最大公因式d(x).nx解： f (x) g(x) 是d(x)的倍式 n!nm n).而L的因式只有

10、两种可能：或是常数C,或是xm(1n!但是 x不整除f (x)，也不整除g(x)d(x) c,即 f (x)与 g(x)互素辗转相除法具有可操作性，较因式分解法适用范围更广，有具体的格式进行操作.但当已知的多项式次数较高时或者多项式的个数较多时，辗转相除次数较多显得十分麻烦； 在求u x ,v X时，辗转相除的过程不能用一个非零的常数去乘除式和被除式，运算困难.因式分解法和辗转相除法在辗转相除法的运算中，*(x)(i 1,2 s)都是f(x), g(x)的最大公因式的倍式.这样，只要发现某一 ri (x)能较快的因式分解，就可用此分解式中不可约因式试除 f (x),g(x)而 得到最大公因式例

11、f(x)2x175x165x15146xc 13122x x1110987x x 10x10x 9x 3x11x510x412x36x26x615141211 107543g(x)2x7xxxx10 xx4x14x 2x 4计算f(x), g(x)的最大公因式解：由辗转相除法得z Xo 15-71412g(x) 2x7xxZ 、17_16-15f (x) 2x 5x 5xx2 x 1q-i x111075,4-14*13121110xx10x x 4x6x 2x x x x314x 2x 4"9“87610x10x 9x 3xRi(x) x2f(x) (x2 x 1)g(x) (X1

12、12)11ri(x) x 2是有理数域上的不可约多项式r)(x)的因式只可能是x112或常数用x11 2试除，得x11 2不整除f (x), g(x)，所以，f(x),g(x)的最大公因式是常数，即f(x), g(x)互素.在了解了用上述格式表示辗转相除法的过程后，我们还可以用另一种更简单，直观的方式来表示这种过程.矩阵法1.求两个多项式的最大公因式2令f1, f2是两个多项式，不妨设f1f2 ,用f1去除f2有f 2f1 g1212,12f，即 f1f2g12人12 .设1g12A1可知A1是可逆阵，再用r12去除f10 10 11 01 0有 f1r12g 21 r21 , r21r12

13、,即f1r12r21 r12.设A2,g21 1g12 1则A2也是可逆阵，依次做下去，由于在绝对递减，必有某时有k1 也0k2 或rk10.不妨设rk1d 0k20,则AsA1A2d 0 . f1 f2 A d 0，其中 AA,A2As是可逆阵设Af1u1f2u2d .又由于 f1 f2d 0 A1 一， -尸是f1,f2均可由d表示,即d是f 2的公因式综合得d是f2的最大公因式例 f1 4x4 2x316x25x9, f2r 322x x 5x4.求f1与f2的最大公因式 d(x)解 f2作除法f1f22x6x23x 9 ，即1f1 f 206x23x9f2 .再作除余法2x1f26x2

14、3x91 1(x1),311即6x2 3x 9f21x336x2 3x9x1 .再作除法,016x23x9x 16x 90,即6x2 3x 9x1100x1 .6x 91则d x x 12.求3个多项式的最大公因式f1 , f2, f3 是 3个多项式，f1 min f1, f2, f3，用f1去除f2 ,f3，有f2f1 g1212 ,f3f1g1313 ,1g 12g131g 12g 13即 f1 f2f3010f1r1213 , A101 0.不妨设00100 1r12minf11213，再用12去除f1和13，有即1ri2g 21r21, ri3gg 23r23 ,f iri2r i3

15、g 2iig 23r2iri200i继续作下去，由于rij绝对递减，必有某时不 妨 设 rk1 d 0,rk2 rk3 0 ， 则 有 f1A1A2AsA A1A2 As A,A2, , As均可逆，则有 fid 00 .设A的第一列r 23 , A 2g 21 1 g 23001rk1,rk2,rk3 中有一个不为零，其余全为零d 0 0 A 1 ，即 f1, f2, f3为 u1,u2,u3, 则 f1u1 f2u2 f3u3 d . 又f1 f2 f3x 2 2x i.均可由d表示，即d是fi, f2, f3的公因式故d是最大公因式例f14x42x316x25x 9,f22x3x2 5x

16、4,f3求fi, f2, f3的最大公因式解 f3最小，用f3去除fi, f2，有f if34x 2 6x8 i7xi7 ,f2f32x 3x1,即i00fi f 2f30i0i7 x i7x 1 f 3 ,x14x26x 82x3i最小，再作除法，i7xi7 x ii70,f3x i x1 0.i00即i7 x i7xif 3i7 ixi0 x i0.00 id x1是最大公因式.3.求n个多项式的最大公因式1, f2, fn是n个多项式,minfi, f2,f n , 用 fi 去除 f2 ,fn , 有fi gi2figi3ri3, fnfiginrin,i g i20if i f 2f

17、 ng in0firi2rin1g12g1 n设 0 1 0 （必是可逆阵） A10 0 1不妨设ri2minfi, g,心，再用去除仃川，rm有f 1 r12 g21r21r13r12g23r23r1nr12g2nr2n即i00rg 2iig2nfiri2rinr2iri2r2n .00ii00设 A2g 2i ig 2n （必是可逆阵） .继续下去，由于rij绝对递减，必00i有 某 时 rii ,rin中只有一个不为零其余全为 零. 不 妨 设 riid 0 ，则fif2fn AiASd00.设A AiA2 As 是可逆阵fif2fn Ad00， 设 A 的第 一 列 为 ui,u2,u

18、n ，有1f1u1f2u2fnun d ，且f1 f2fn d 00 A 1 ,f1, f2,fn均可由d表示，即d是fi, f2, fn的公因式故d是最大公因式矩阵法在辗转相除法的基础上，结合多项式最大公因式的定义与矩阵的运算性质， 不紧可以求两个多项式的最大公因式还可以求得多个多项式的最大公因式并同时求得d x关于 fi x i i,2, ,n 的线性组合 . 虽采用的是矩阵形式，但仍需要两两多项式作除法， 随着多项式的个数增加计算量大大增加，计算过程比较复杂 .矩阵的初等行（列）变换法定理 2 设 Afi x , f2 x , fn x i n 是 Px 上的非零阵，经过一系列初等列变换

19、可化为而R x的第一列元素就是Ui x i 1,2, n，使得f1 x u1 x f2 x u2 xfn x un x d x成立例对于整系数多项式x3x25x 2;3xxx x 2;x2x4323x x 6x求它们的最大公因式 d xf1f2f3100解令 C对其进行如下的的列初等变换：010001f1f2f3f1f22x23x2C1002x 1 |2310013 1010012x10010012x 2x f22x2 3x2x2 2xx 2x21 002|1| |1|,1 x|1| |2|11 x2x3 1,13 122x 112x12x 12x2 x16x31 011x 1300x 21x

20、2002x 1x 121,32x12x 16x2 x 12x25x26x 36x32x25x 26x2 x 13x 1x233x23x 12x12x 1其中，R x6x 32x25x 26x2 x13x23x 1d x 是唯变换过程中，系数保持是整数，在这个原则下可以随意地作初等列变换，得到的 一的 .但由于作法不同，得到的 R x 的第一列元素 ui x i 1,2, ,n 可能不同，故线性表 示不唯一，但都能使f1 x u1 x f2 x u2 x f3 x u3 x d x 成立 .矩阵的初等变换法通过直接构造矩阵， 利用多项式矩阵的初等变换一举求得最大公因 式 d x 及其线性表达式，

21、具有较广的使用范围且运算过程较灵活，避免了多项式之间繁琐 的除法运算 . 但由于构造的是多项式矩阵， 故在运算过程中仍是多项式的运算， 有一定的难 度.3. 6 矩阵的斜消变换基于矩阵的初等行， 列变换法， 我们思考是否存在一种运算过程来避免多项式之间繁琐 的除法运算定义3 设 t(x) ai1xn ai2xn 1ai,n 1x ain,(i 1,2, ,m)为 口个多项式(至少有一个多项式不为零)，A (aQ为m n阶矩阵，a为与多项式fi(x) , ( i 1,2, ,m ) 相对应的矩阵 .若 A 的第 i 行从左向右第一个不为零的元素为 ai,s 1, 第 j 行的第一列元素 aj1

22、不为零 (i j) , 则称将第 i 行的 n-s 个元素： ai,s 1,ai,s 2, ,ain 乘以 c 斜加到第 j 行元素： Sa j1,aj 2, ,a j,n s 上的变换为第 i 行到第 j 行的左斜消变换记为 L ji (C) ；若A的第i行从右向左第一个不为零的元素为 ais， 1 s n ,第j行的第n列元素 a jn (i j) 不为零，则称将第 i 行的 s 个元素： ai1,ai2, ,ais 乘以 c 斜加到第 j 行元素： aj,n s1, ,ajn上的变换为第i行到第j行的右斜消变换，记为 Rj；s(C)此外，对 A 施行矩阵的第一，第二种初等行变换以及左斜消

23、变换和右斜消变换不改变A化简成如下形式的矩阵:与其对应的这些多项式的最大公因式，并且总可以将矩阵C=1 b200bi 10此时( f1(x), f 2(x),例 用矩阵的斜消变换求f(x) x4 4x3 2x2 4x1424解A=01410121012301121212011L102 (1), L302 (1)112000111100000000fm(x)i1xb2xi2bi 1.2 g(x)3x4x2x6h(x)x32x2 x 2求(f (x),g(x),h(x)300123L112(61), L023 (1)0022420121201231231L132(1)011211201121120

24、1111L121 ( 1)02222L021(2)00000所以， ( f ( x), g ( x), h(x) x 1我们约定，用左斜消变换化简矩，若所得矩阵的前若干列元素全为零时，要及时消去这些列再做变换； 用右斜消变换化简矩阵时， 若所得矩阵的后若干列元素全为零时， 要及时消去这些列再做变换 . 这样可以达到简化矩阵的目的在用斜消变换化简矩阵时，我们会发现，求某些多项式的最大公因式时，需要选择其 适用的是左斜消变换还是右斜消变换 . 并且左右斜消变换是不能同时使用的，这就给我们解 决某些问题时带来了局限性 .若用矩阵A=anan 1a1a0表示多项式：f ( x)nn 1an xan 1

25、xabnbn 1b1b0g( x) bnx nbnn11 xn 1b0的待求最大公因式. 则对 A 施行初等行变换，不改变两个多项式的最大公因式0时，anan 1a1a0ana n 1a1 a0当 a010 ，即它们表示的bnbn 1b1b00bn 1b1 b0两个多项式的待求最大公因式相同 .利用以上结论， 就可以利用矩阵的初等行变换求出一元多项式组的最大公因式， 其一般步骤为：将系数矩阵A利用初等行变换化为阶梯矩阵B. 考察矩阵 B ，若出现元素都是 0 的行，则去掉该行；若某行变为00 k k 0 时，多项式的最大公因式为 1，计算终止；若出现每一行的列数最大的非零元素不在同一列时， 则

26、施行右对齐； 若每一行的列数最大的非零元素在同一列时， 则 施行左对齐；将 B 变成非阶梯矩阵，然后，以非零元素最少的行将其再化成阶梯矩阵. 反复循环上述步骤，直到 A变为1 n 1型矩阵，则对应的多项式即是的最大 公因式 .例设 f (x) x3 3x2 2x 6, g(x)x3x2 2x 2,(f (x),g(x)=解：对矩阵13A=26 施行初等行变换及替换：112213 2 61326A04 0 80102102001 0 2010201 0 201020000故，( f ( x), g( x) (x 22,0)x 2 2例f (x) x 44x32x 2 4x3g( x) x 3 4 x2 xh(x)ox2x厶x2求( f(x),g(x),h(x)解1424314243A=01416014160121200224142431120011 2 0 0141601416003 3 6 0224001424300 1 2 30011200112003360001100123000000011200022001100011000000000000002200011'00011000000000000000所以，( f ( x), g ( x), h(x)x1数值矩阵法根据多项式与其系数间的一一对应关系，构造多项式组的系数