多项式最大公因式最优求法的探讨

唐山师范学院本科毕业论文题目多项式最大公因式最优求法的探讨学生陈静莎指导教师孙秀娟讲师年级2009级专业数学与应用数学系别数学与信息科学系唐山师范学院数学与信息科学系2013年4月郑重声明本人的毕业论文（设计）是在指导教师孙秀娟的指导下独立撰写完成的如有剽窃、抄袭、造假等违反学术道德、学术规范和侵权的行为，本人愿意承担由此产生的各种后果，直至法律责任，并愿意通过网络接受公众的监督特此郑重声明毕业论文（设计）作者（签名）年月日目录标题多项式最大公因式最优求法的探讨1中文摘要1引言11基本概念12最大公因式的求法521辗转相除法522因式分解法723多项式组合法824等效变换法1025矩阵初等变换法133优劣性比较194结束语22参考文献23致谢24外文页25多项式最大公因式最优求法的探讨陈静莎摘要本文介绍了多项式最大公因式的几种常规求法，如辗转相除法、因式分解法、多项式组合法、矩阵初等变换法、等效变换法等，对这些方法进行了详细的证明，由这些方法得出了求最大公因式的一些性质，通过讨论，文章浅析了某些具体多项式应采取的简便的求最大公因式的求法此外，本文通过具体实例对最大公因式的各种求法的优劣性进行了比较，进而探讨出某些具体多项式最大公因式最优的求法关键词最大公因式辗转相除法因式分解法组合法初等变换前言多项式理论不仅是中学代数的主要内容之一，也是高等代数的的重要组成部分，它在数学的理论与应用中都有十分重要的意义，而求最大公因式在多项式理论研究中又占有显著地位一元多项式最大公因式的解法，在各种高等教材中已经做了许多基本方法的介绍，但在我们的实际应用中，这些基本方法存在运算过程复杂，计算量大等缺点所以，探讨求最大公因式快速、准确、简便的方法就尤为重要多项式的最大公因式作为多项式理论中的核心部分，是一个一直受到人们关注的古老而又始终充满活力的研究内容多项式的最大公因式的常规求法有辗转相除法、因式分解法和组合法，前人对这些求法及其简单应用都做了较深入的研究而初等变换求法作为计算最大公因式的一种简便方法，克服了传统的辗转相除法及因式分解法带来的繁冗性和复杂性初等变换在几何和矩阵理论的研究中有广泛的应用，因此讨论其性质及其应用具有重要意义1、基本概念设是一个数域，为数域上的一元多项式环，有如下定义和定理PXP定义1设、是中的两个多项式，如果满足是、的公因式，FGDXFGX且、的公因式都是的因式，则称多项式是、的一个最大公因式FXGDXF定理1对于中的任意两个多项式、，在中存在最大公因式，且PFXGPXDX可表成、的一个组合，即存在多项式、满足DXFXUVDXUFVX证明（1）假设、有一个为零，不妨设，则可知是一个最大公因式，显FXG0GXFX然存在多项式，满足1UV1FF（2）假设、全不为零，利用带余除法FX用除，得到商，余式，此时若，可得，即G1QX1RX10RXGXF是一个最大公因式，可求得多项式，满足式；XUVQ若，就用除，余式，若，可得，即是一个10R1RXG2RX21RX1RX最大公因式，可求得多项式，满足式；1VQ若，就用除，得到商，余式，RX2RX13X3RX以此类推，所得余式的次数不断降低，即12GR但的次数有限，因此在辗转相除有限次后，必有一余式为零，GX于是可得1FXGQXR2221IIISRXQXR21SSSSRR10SSXQX由（1）可知是、的一个最大公因式SRXFG下证存在多项式、满足式，UV事实上，变形上面倒数第二式有，同理可解得21SSSSRXRXQ、将解得余式代入上面的运算式，并逐个消去，即可得定理1的式1SRX2S证毕2、主要方法及证明由定义1可知，若、是、的两个最大公因式，则必有，1DX2FXG12DX，而又由整除的性质可得，其中是非零常数由此有两个不全为2DX21DCC零的多项式的所有最大公因式均只相差一个非零常数倍，那么，根据此性质，首项系数为1的那个最大公因式是唯一确定的，且记为FXG，现约定下文所提及的最大公因式均指首项系数为1的那个最大公因式21辗转相除法由定理1的证明可以很容易得到求最大公因式的一种有效方法辗转相除法例1在有理数域上，求多项式、的最大公因式，其中表达式分别为FXG，43221FX4323X事实上，多项式的最大公因式只相差一个非零常数倍，因此在计算过程中可以适当的用某一常数乘以多项式的各项系数，从而化简计算量且不改变最大公因式的值，因此利用辗转相除法解用除得商，余式，GXF12QX321450RXX再用除得商，余式，1R2521再用除得商，余式，2X13X30RX由此可得是、的一个最大公因式，2RFG即1FXGX，例2多项式、同上面的例1，求多项式、使其满足定理1的式FUXV解利用例1的计算过程扩大某一多项式的倍数，此时可计算出多项式、使其满足UXV定理1的式，且可得如下等式2FXGX，1QR2XRX其中，同例1，131RX2由有且代入1FXGQXR得12FQXR即2X又知，将上式化简可知满足的项式2FG，DXUFVXG、分别为，UXV25UXQX121VQ但是，将、代入进行检验得VFGX21XFGXD所以，此时计算的多项式、并不满足定理1的式UVX事实上，在计算过程中若不扩大某一多项式的倍数，经过计算有32245FXGX3281X由，可得211582XXFG化简可知满足的多项式、为DUFVGUXV，2X1X分析若用例1计算过程所得商和余式求多项式、，那么所得结果将错误，这是因XV为在例1的求解过程中，为了简便运算而将多项式扩大了某一常数倍，因此应按照辗转相除法的一般步骤进行求解现考虑个多项式的最大公因式N,21XFFXN定理2中的任意个多项式有P,21XFN，其中2,2121FXFFXFNNN分析容易推出，是多项式的一个最大公因式，那么与多0D,21XFN0DX项式的最大公因式也是多项式的最大公因式这样，由于两个多项式NFXXF的最大公因式总是存在的，所以个多项式的最大公因式也总是存在的，并且可以累次应用辗转相N除法来求出证明在此不再赘述注意与两个多项式的情形一样，个多项式的最大公因式也只有非零常数因子的差别我们N约定，个不全为零的多项式的最大公因式指的是最高次项系数是1的那一个那么个多项式NN的最大公因式就是唯一确定的,21XFFXN有计算过程可见，当求三个以上多项式的最大公因式时，运用辗转相除法计算相当繁冗并容易出错；除此之外，若又要求将表示成的形式时，此时，在辗转相除法的DXUFXVG过程中不能用一个非零的常数去乘以除式或被除式，这就使得计算更加困难22因式分解法在高等教材中已明确提出，利用多项式的标准分解式可以很快的得到它们的最大公因式又因为多项式的最大公因式不会随着数域扩大而发生改变，所以尽管多项式在不同的数域上标准分解式不尽相同，但这不影响多项式的求解因此只考虑在中，以两个多项式、为例，PXFXG设、的标准分解式分别为FXG21XPXAPSMM21XPXBGSNN其中、分别是、的首项系数，是两两不等的首项系数为BF1S1的不可约多项式，是非负整数，则1S1NS12,RKKKFXGPXPX这里MIN,IIK因式分解法可推广到个多项式的情形，其方法与两个多项式的情形相同，这里就不再赘述例3设，用因式3215FXX2215FX323410FXX分解法求多项式，的最大公因式2F3解将，进行因式分解，可得在有理数域上的标准分解式分别为1FXX2151F23X23FX故可得123,5XF例4设，3215FXX322915FXX，用因式分解法求多项式，的最大公因式34FXF2F3FX解将，进行因式分解，可得在有理数域上的标准分解式分别为1F2FX3F2151X2F23XX故可得123,5FF例5设，为两个非零多项式，证明存在自然数，使任意的大于的两个自FXGNN然数，都有1N212,NNFXG证明设，若，则结论显然成立FXD1若，则令DX由例3、例4可知，对于因式分解法的前提是，必须求出多项式的标准分解式事实上，并不是所有的多项式都能进行简单的因式分解，就算可以因式分解其过程也是相当复杂，而一般没有一个切实可行的方法对多项式进行因式分解因此，求最大公因式一般不用此种方法，它提供的方法主要是用于理论证明，不用于求解具体的多项式的最大公因式，更不用说求出满足定理的多项式、UXV23多项式组合法先给出定理1的三个简单推论推论1定理1的逆命题对任意的多项式、，不一定是多UXVUXFVGX项式、的最大公因式此命题为假命题FXG例如多项式，可知、互素，此时对任意的，FX1GXFXGUX，显然不是、的最大公因式1VXUV推论2多项式为、的最大公因式，则DXFXDXUFVXG推论3对任意的多项式、的任一个组合是UXVFXGUXFVGX、的最大公因式的倍式FXG由上两个结论知、的最大公因式一定是、的组合式FXGFX由此可得定理3在辗转相除法运算式中，都是、的最大公因式1,23IRSFXG的倍式DX证明利用辗转相除法计算最大公因式可得如下运算1FXGQXR2221IIIRXQXR21SSSSRR10SSXQX即得SRD将上式运算变形得，它是、的组合11XFGXFXG则是的倍式R将代入运算式得1RX2211XQXRFXQX12G由等式可知是的倍式2RXD以此类推都是、的最大公因式的倍,3,ISFXDX式证完例6在有理数域上，求多项式，21MXXF的最大公因式3211MXXG解根据题意计算，可得出FG1FXG由推论3可知是最大公因式的倍式，而1又在有理数域上的因式只有一种可能，即常数，FXGC所以所求的最大公因式为DX例7在有理数域上，求多项式、的最大公因式，其中FGX1615413219876542430376FXXXX5207543GX解由题意可得2126FXG其中余式为由113R艾森斯坦判别法知是有理数域上不可约多项式，26X则的因式只能是或者是常数，用试着去除可知不整除1RX1212XGX12GX所以、的最大公因式应该是常数，FG即为DX由以上两个例子可见在辗转相除计算过程中若发现有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得到最大公因式，并且当、的次数很高时用FXGFXG此方法较为方便若是求个多项式，的最大公因式时，有如下定理N1F2FXN定理4设中的多项式，在辗转相除法所得运算式中，PX1FX2FNFX都是，的最大公因式的倍式IRX,2,1SDX此命题直接为定理3的推广，不再赘述证明过程由以上讨论结果可知，当求个多项式的最大公因式时，这种方法相比于辗转相除法两两求最N大公因式的运算量已经大大减少，但是这种方法只适用于余式能较快因式分解的情形，故此法具有一定的局限性；而且当2时，求多项式、满足定理1的式，此方法却不适用UXV24等效变换法定义2设，NNAXAXF10NNBXBXG10称矩阵为、的矩阵，记作则NBA10F,FM与等效，从而、的最大公因NBAAXGFMA10,01TKFXG式，这就是等效法求解最大公因式，该方法虽然克服了辗转相除TTTKF,法的来回计算在求解有了很大的进步，虽然该方法也可以推广到求个一元多项式的最大公DXN因式，但是美中不足的是，它没有求解出满足成立的21XDUFUFXFN,21,IXUI任给一个矩阵，则显然存在多项式、，使1NAFG,AMFG定义3设，若，则称与等,MFG1,BFG1,XFXAB效，记作AB定理5若矩阵经过三种初等变换变成，则与等效,F1,BFG证明若变换的两行得到，则，显然，所B,MF,XGXF以与等效AB若的第一行乘以加到第二行得，则，由最大公因式的性质KKFG，所以与等效,FXGMFXGXAB若的第一行乘以非零数得，则，又AKMKFX，所以与等效,FXKFX定理6若，其中，NBAGFM10,0210BABN0N则与等效AB证明由条件，则NNAXAXF10NNXXG10，所以因为，则与互素，故1BXGNN,BFNAFX，即与等效,FXGFXGAB例8已知，求4321X321GXX,FXG分析此题只求和的最大公因式，并没有要求求解出满足F,F的、,FXGDXUVXUXV解1341,0AMFG1341020312010所以,1DXFGX25矩阵初等变换法基本概念本文以表示数域上的一元多项式环PX定义7以中的一元多项式为元素的矩阵称为多项式矩阵设PX的个一元多项式，规定符号表示这个,21XFXFNN,21XFFXN一元多项式的最高系数为1的最大公因式，则有以下性质DX性质12,1IJNJIFXFXFFXFIJN性质12,1,0INFXFXFFCXINCP性质12,IJNJNFXFXFFFCXFIJN多项式矩阵的初等变换多项式矩阵的初等变换矩阵的某一行（列）乘以非零常数矩阵的某一行加另一行的倍，其中是一个多项式XX多项式矩阵的性质性质每个可逆的多项式矩阵都可以表示成一些多项式式初等矩阵的乘积；性质对一个多项式矩阵施行初等变换，不改变每个列向量的多项式的最大公因式；性质设为多项式矩阵，则存在可逆的多项式矩阵，使得为阶梯型矩阵APA综上可得交换两个多项式的位置，不改变其最大公因式；将某一多项式乘以一个不为零的常数，不改变最大公因式；将某一项的倍，加到另一个多项式上，不改变其最大公因式，对C0比代数理论的矩阵的初等变换，上述性质恰好都满足主要定理及证明定理7设，其中，FXAG12PP0FXG且可逆，若,12IJPXPIJP1122,0DXPXAE其中是首项系数为1的多项式，则有，且，DX,FG1UXP，使成立12VPUXFVGX证明对于，存在，使得0F,UVPX,UXVGXFXD令，其中分别为1PXU12PXV21GXPABD2FXPABD,AB的首项系数，则有,FGPAE,11211222PXFXGPX0UFVUVGXFABD1122DXPX所以，且，使,FG1UPX12VPX成立DXUVX定理8是任意个多项式，12,NFF，1FXXXUDX若经过矩阵的适当初等变换，可以变换为12NNFAEFXA其中是阶单位矩阵10NDUXBMNE证明若时，则，已有的形式120NFXFFX0DXAB不全为零时，则必有一个次数最低的多项式，不妨设为，对12,NF1FX分别乘以一个适当的多项式，消去的每个最高项，这时矩阵的第一列变为X2,NFXF，其中12,NFRX12,3IIIFXQR当时，其中02,3II1DCFXCP不全为零时，继续重复因为次数都是有限的，23,NRXRX12,NFXFX所以经过有限次后，必然能够出现矩阵B中第一列只有一个元素，其他元素全为零，0K此时即有，其中DXCKCF上述过程用矩阵的初等变换表示为11222NNFXRXRPAMAMA行初等变换行初等变换110KQXZXA行初等变换10NKDXUXM行初等变换定理9定理8中满,12,IUXN足12NFXUFXFXUDX证明设，由于对矩阵的初等变换相当于在它左边乘上对应12C的初等矩阵，所以，存在可逆矩阵，使得P且于是，比较对应位置的元,PEB12NUXUX0DXPC素得到12NFXFXFXDX最大公因式的矩阵初等变换法将矩阵，经过初等行变换化为矩阵12NNFXAMEF，则是的最大公因式，且10NDXUXBMD12,NFXFX12NFXUFXFXU应用举例例9求和的最大公因式，其中FGD，4321FXX321XX分析此题只求和的最大公因式，并没有要求求解出满足F的、，而是对于两个多项式来说的，因为我们可以用多种DXUFVXGUXV方法进行求解，在此，运用矩阵的初等变换法进行求解解124323240101PXAXX1232123201PXX212213XX2122XX122314PX212323447XX21223106XX12323434XX所以DX例10设，43243FXX3246GXX求32HXX,FGXH解14314230601624A141420230103661232010021000所以，,1FXGHX例11，432143322543FXX，求，并求出、使得3236FXX1,FX1U23UX123123,FFUFX分析此题求解的是，并且还要求解满足3,XF的、，此时若用123123,FXFXFXFUX12UX3辗转相除法、因式分解法、多项式组合法、等效变换法、矩阵斜消变换法就非常的困难了，所以最佳的选择就是矩阵的初等变换法解432431056XXA133246101534PXX32123176102453XXX12243119104PXX23217365247PXXX2123109461XX1322812750PX71213222617751XXXXX1532226110757XXX1222101757XXX，且有，使得123,FXFX12UX2X32XU成立13FFF对于求解此类多项式我们最佳方法就是矩阵初等变换法，它就是利用矩阵的初等变换，一步一步求解，而且同时求解出满足的最大公因式系数123123,FXFXFUXFXFUX三、优劣性比较由上文我们已经总结出5种求多项式的最大公因式的有效方法，当多项式个数、次数不同时，各个方法中均有其使用条件限制或者使用范围，现以一下两方面为例进行探讨，如下表所示方法简便求最大公因式的条件DX限制或使用范围能否求解出，1UX满足MFXFDX辗转相除法多项式次数较低，并且多项式的个数不超过三个能，但是其求解过程不能用一非零数乘以除数或者被除数因式分解法要求题中所给多项式在数域上均能分解，利用因式分解法必须求出多项式的标准分解式否多项式组合法有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得到最FXG大公因式，并且当、F的次数很高时用此方法较GX为方便多项式表达式较为特殊，个数少，最后所得组合简便否矩阵的斜消变换法将多项式的系数写成对应矩阵的形式，且系数较简便计算否矩阵的初等变换法表示成多项式矩阵或者对应系数矩阵的形式均可能，但是要求表示成矩阵的形式进行初等变MFXE换通过上述表格两方面的简单比较可以探讨出每一种方法均有其优缺点，现将探讨所得简单结果列表如下方法优点缺点辗转相除法适合于所有形式的多项式，具体的可操作性比较强，在任何数域上都具有固定的格式求解，求解步骤也固定，并且能直接求得多项式，1UXMX计算过程比较繁琐，当所求多项式个数较多、次数较高时，计算量相当的大，书写过程繁冗很容易出错，尤其是在，1UX，的求解过程中不能MUX用一非零数乘以除数或者被除数因式分解法形象直观，看上去整齐，运用的原理比较简单，且容易看懂要求题中所给多项式在数域上均能分解，利用因式分解法必须求出多项式的标准分解式，所以此方法只适用于能够因式分解的多项式，对其他的多项式时失效，另外，此方法也不能直接求出，1UXMX多项式组合法不用将辗转相除法进行到底，若有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得FXG到最大公因式，并且当、F的次数很不是很高时用此GX方法较为方便，运算量大大减少当多项式不是特殊形式，并且次数很高时，或者余式都不能分解时，此方法就不能快速求解出最大公因式，而且此法也不能直接求出，1UXMX等效变换法此方法不论多项式次数高与低都适合，计算过程也简便，不容易出错对于多项式的系数特别大的计算式就不简便了，此方法的局限性是一般只适合求解两个多项式的最大公因式，而且此方法也不能直接求出，1UXMUX矩阵的初等变换法结合多项式最大公因式的定义与矩阵的运算性质，不但可以求多个多项式的最大公因式、计算过程简单，而且可以直接利用初等变换求得，1UXMUX在多项式矩阵的运算过程中，也容易出现计算错误若写成对应系数矩阵的形式时，不能直接求得，1UXMX通过上述表格所对比的结果我们可知在求解多项式最大公因式时，应根据实例中多项式的具体表达式、多项式个数的多少、多项式次数的高低以及多项式系数的大小来灵活选择不同的方法来求解，用适合多项式本身特点的求解法，以达到简化计算量且提高准确率的目的四、结束语本文通过对多项式最大公因式最优求法的探讨，经过对比，得出简单结果，可知对于不同的多个多项式在求解其最大公因式时有不同的解法，需要我们具体问题具体分析，运用最适合的方法求解简化计算量、提高准确率在平时只有训练掌握各种解法，才能在具体求解时选择最优解法最后需要指明的是，到目前为止多项式最大公因式的求法已有很多，但针对不同多项式时采取何种算法求解却还没有一般的可行的方法，如何求特殊多项式的最大公因式及其理论证明还有待于进一步研究、丰富和完善参考文献1张禾瑞，郝炳新高等代数（第四版）M高等教育出版社，1999，38802北京大学数学系几何与代数教研室代数小组高等代数（第三版）M高等教育出版社，2003，12293邱森，高等代数M武汉大学出版社，2008，4354684沈文选，矩阵初等应用M湖南科学技术出版社，1996，711065刘国琪，多项式的最大公因式的一种新求法J工科数学，1997，（02）6刘国琪利用矩阵的初等行变换对矩阵的特征值与特征向量的同步求解数学通报，21996，P40427杨刚，最大公因式的矩阵求法J甘肃科学学报，2003，（03）8郁金祥基于矩阵斜消变换的最大公因式求解J数学的实践与认识，2005119郁金祥一个求最大公因式的方法J嘉兴学院学报，2001，310张庆，王朝霞求两个多项式的最大公因式的新方法11钱吉林高等代数题解精粹M北京中央民族大学出版社200212王恩平，王朝珠多项式与多项式矩阵北京国防工业出版社，199213北京大学数学系高等代数第三版M北京高等教育出版社，20031218北京大学教学系高等代数第儿版北京高等教育出版社14北京大学数学系几何与代数教研室代数小组高等代数M第2版，北京高等教育出版社，1988121815北京大学数学系几何与代数教研室代数小组高等代数M北京高等教育出版