多项式辗转相除法求最大公因式

求最大公因数的三种方法最大公因数（GCD）是两个或多个整数的最大公约数。

计算最大公因数在数论和数学问题中非常重要，它有助于简化分数和化简多项式等。

在本文中，我们将介绍三种常见的方法来计算最大公因数。

方法一：质因数分解法最常用的方法之一是质因数分解法。

该方法基于一个简单的事实：如果一个数可以被另外一个数整除，那么这个数的因数也一定能够整除它。

质因数分解法的步骤如下：1.将待求的两个数进行质因数分解；2.找到它们共有的质因数；3.将共有的质因数相乘，得到最大公因数。

例如，我们要求解48和60的最大公因数：48=2×2×2×2×360=2×2×3×5它们的最大公因数为2×2×3=12方法二：辗转相除法（欧几里德算法）辗转相除法，也被称为欧几里德算法，是一种用于计算两个数的最大公因数的方法。

这种方法的基本原理是，如果一个数能够整除另一个数，那么这两个数的最大公因数就是能够整除两个数的最大数。

辗转相除法的步骤如下：1.将待求的两个数进行除法运算，得到商和余数；2.将除数作为被除数，余数作为除数进行下一轮运算，重复第一步；3.直到余数为0，这个时候最后一个非零余数的除数就是最大公因数。

例如，我们要求解48和60的最大公因数：60÷48=商1余1248÷12=商4余0因此，48和60的最大公因数为12方法三：更相减损法更相减损法，也是一种计算两个数的最大公因数的方法。

该方法的基本原理是，两个数的差是它们的公因数，因此公因数的最大值一定是这两个数的最大公因数。

更相减损法的步骤如下：1.将待求的两个数进行减法运算，得到差；2.将差作为新的较大数，原来的较大数作为新的较小数，重复第一步；3.直到两个数相等，这个时候它们的值就是最大公因数。

例如，我们要求解48和60的最大公因数：60-48=1248-12=3636-12=2424-12=12因此，48和60的最大公因数为12总结：这三种方法是求解最大公因数最常见和常用的三种方法。

#include<stdio.h>#include<stdlib.h>#include<math.h> struct chain // 定义一个多项式的结构体{int n; // 该多项式的最高次数double *an; // 存放多项式的系数};void creat_chain(struct chain *c) // 建立一个多项式{int i,n;double ai;printf(" 请输入该多项式最高次数:");scanf("%d",&n);(*c).n = n;(*c).an = (double *)calloc(n+1,sizeof(double)); // 给该多项式系数动态分配内存printf("按下列格式输入系数:(例如x^4 + 2x^3 - 7x^1 + 5 输入:1 2 0 -7 5)\n"); printf(" 等待输入:");for(i=n;i>=0;i--){scanf("%lf",&ai);(*c).an[i] = ai;}}void show(struct chain c) // 按照多项式的格式显示多项式{int i=c.n;printf(" 多项式是:");while(i>=0){if((i!=c.n)&&(c.an[i]>=0))printf(" + ");switch(i){case 1:printf("%.2lfX",c.an[i]);break;case 0:printf("%.2lf",c.an[i]);break;default:Pri ntf("%.2lfX^%d",c.a n[i],i);break;}i--;}Printf("\n");void do_add(struct chain *ch,struct chain ch1,struct chain ch2) // 两个多项式求和 {int i;if(ch1.n>=ch2.n){(*ch).n = ch1.n; // 求和之后多项式的最高次应是 ch1 和 ch2 中较高的次数 (*ch).an = (double *)calloc((*ch).n+1,sizeof(double));for(i=0;i<=(*ch).n;i++){if(i<=ch2.n)(*ch).an[i] = ch1.an[i] + ch2.an[i]; // 相同次数的系数相加 else(*ch).an[i] = ch1.an[i];ZZ 直接保ch1中有而ch2中没有的项的系数}} else ZZ 与上面 if 相反{(*ch).n = ch2.n;(*ch).an = (double *)calloc((*ch).n+1,sizeof(double)); for(i=0;i<=(*ch).n;i++){if(i<=ch1.n) (*ch).an[i] = ch1.an[i] + ch2.an[i];else(*ch).an[i] = ch2.an[i];}}}void check_change(struct chain *r)ZZ 检验多项式 r 的最高次数并进行相应的修改{ int i = (*r).n;while((fabs((*r).an[i])<=1e-5)&&(i>=0)) ZZ 依次从高次项向低次项进行系数检验i--;(*r).n = i; ZZ 注意：如果多项式 r 为O ,这里i=-1}if(fabs(r.an[i])>=1e-6) // 如果一旦有一个不为零，返回 false return false;return true; // 全为零的情况下返回 true}void do_div(struct chain ch1,struct chain ch2) // 辗转相除法 ,公式 :ch1 = q*ch2+r; {int i = 0,j;double tmp;struct chain q,r;if(check_zero(ch2)) // 判断所除的多项式是否为0，若为 0，退出 ;{ bool check_zero(struct chain r){ int i;for(i=O;i<=r.n;i++)ZZ 检验多项式 r 的最高次数printf(" 所除的多项式不能为0!\n");exit(0);}q.n = ch1.n - ch2.n; //q 的最高次数为ch1 和ch2 最高次数相减r.n = ch1.n - 1;r.an = (double *)calloc(r.n+1,sizeof(double)); // 为系数动态分配内存q.an = (double *)calloc(q.n+1,sizeof(double));while(i<=q.n){r.n = ch1.n - 1; //r 的最高次数为ch1 的最高次数减1 q.an[q.n-i] =ch1.an[ch1.n]/ch2.an[ch2.n]; // 多项式q 的最高次项系数tmp = q.an[q.n-i];for(j=r.n;j>=0;j--){if(j>=q.n-i)r.an[j] = ch1.an[j] - tmp*ch2.an[j-q.n+i]; // 高次对应相减elser.an[j] = ch1.an[j]; // 低次保留}if(check_zero(r)) break; // 若余式r 系数全为零,退出循环ch1 = r; /∕ch2没除干净，将r赋给chi,继续除ch2 i++;}printf(" --------------------------------------------\n");printf("q(x):");show(q); // 显示每一步的多项式qprintf("r(x):");show(r); // 显示每一步与q 对应的多项式r printf(" \n");check_change(&r); // 修改余式r 的最高次数，即修改r.nif(r.n==-1) //r.n==-1 时，说明最大公因式已经找到{printf(" 所求最大公因式的");show(ch2); // 输出结果free(r.an); // 回收动态分配内存}elsedo_div(ch2,r); // 辗转相除}void main(){struct chain ch1,ch2,ch;printf("*************** creat_chain(&ch1); show(ch1);printf("*************** creat_chain(&ch2); show(ch2);printf("*************** do_add(&ch,ch1,ch2); show(ch);printf("*************** do_div(ch1,ch2); 建立第一个多项式**************\n\n");建立第二个多项式**************\n\n");以上两个多项式求和**************\n\n");以上两个多项式求公因式**************\n\n");// 回收动态分配内存free(ch1.an);free(ch2.an); free(ch.an);}。

初中数学如何找到一个多项式的最大公因式
要找到一个多项式的最大公因式，可以采用以下方法：
1. 因式分解法：
首先，将多项式进行因式分解，将其写成若干个因子的乘积形式。

然后，找到这些因子中的公共因子，将其提取出来，即可得到最大公因式。

2. 辗转相除法（欧几里得算法）：
辗转相除法也可以用于多项式的最大公因式的求解。

将两个多项式进行相除运算，直到余式为0。

此时，最后一次相除的除数即为最大公因式。

3. 多项式的公共因式法：
对于多个多项式，可以逐步寻找它们的公共因式。

首先，找到其中两个多项式的最大公因式，然后再将这个最大公因式与下一个多项式进行求最大公因式的运算，直到所有多项式都被考虑完毕。

这样得到的最大公因式即为所求。

4. 使用多项式的因子定理：
多项式的因子定理可以用于求解多项式的因子，进而得到最大公因式。

根据因子定理，如果某个数是多项式的根，那么这个数可以整除多项式。

因此，通过尝试多项式的可能根，找到其中能够整除多项式的数，然后将这些数与多项式进行除法运算，找到最大的公因式。

需要注意的是，对于高次数的多项式，可能需要使用更高级的方法来找到最大公因式。

此外，在实际求解中，可能需要使用计算工具、计算机软件或在线计算器等辅助工具来进行计算。

希望这个解答对您有所帮助。

如果您还有任何问题，请随时提问。

多项式最大公因式的求法定理1设)(x)(n ,f (x),(x),f f n 221≥ 是P[x]中n 个多项式.P[x]中多项式d(x)称为)(x)(n ,f (x),(x),f f n 221≥ 的最大公因式，如果它满足下面的两个条件：(1)d(x)是(x),f (x),(x),f f n 21的公因式. (2)(x),f (x),(x),f f n 21的公因式全是d(x)的因式.定理2 设)(),(),(x h x g x f 是][x P 中的多项式，P[x]中多项式d(x)是)(),(),(x h x g x f 的最大公因式，c 是任意的非零常数，则有))(),()()(())(),(()(x g x g x h x cf x g x f x d -==.证明：当)(x f 、)(x g 有一个为零，例如0)(=x g ，那么结论显然成立. 当0)(≠x g 时，则有)()(x f x d ，)()(x g x d .从而)()()()(x g x h x cf x d -，即)(x d 是)()()(x g x h x cf -与)(x g 的一个公因式，令)()()()(x g x h x cf x c -，)()(x g x c .根据整除的性质，我们有)()(x f x c ，所以)()(x d x c .所以))(),()()(())(),(()(x g x g x h x cf x g x f x d -==方法1：用辗转相除法求最大公因式引理 如果)3(121≥n (x),f (x),(x),f f n- 的最大公因式存在，那么)2(21≥n (x),f (x),(x),f f n 的最大公因式也存在，且(x)) (x)),f ,f (x),(x),f ((f (x))(x),f ,f (x),(x),f (f n n-n n-121121 =. (1)证明：由题意，假设(x),f (x),(x),f f n-121 的最大公因式为)(1x d ，那么(x)d 1与(x)f n 的最大公因式)(x d 也是存在的. (2)又由(1)、(2)式，可知n)i (x), (d(x)|f i ≤≤1.假设c(x)是)(x)(n ,f (x),(x),f f n 221≥ 的一个公因式，由(1)式可得(x)c(x)|d 1.这样c(x)就是(x)d 1与(x)f n 的一个公因式，再由(2)式可得c(x)|d(x).所以(x)) (x),f ,f (x),(x),f (f d(x)n n-121 =.定理3 设)2)((,),(),(21≥n x f x f x f n 是][x P 中的n 个多项式，则在P[x]中存在一个最大公因式d(x)，且d(x)可以表示成(x),f (x),(x),f f n 21的一个组合，即有p[x]中多项式(x),u (x),(x),u u n 21使(x)(x)f u (x)(x)f u (x)(x)f u d(x)n n +++= 2211.由定理3对一般情况，设11110110(),()n n n n n n n n f x a x a x a x a g x b x b x b x b ----=++++=++++，不妨设mn ≥则，))(),()(())(),((x g x g x x f a b x g x f m n n m --=.记)()()(1x g x x f a bx f m n nm --=，令01111)(c x c x c x c x f k k k k ++++=-- ，则m k ≤，故))(),(())(),((1x g x f x g x f =))()(),((111x f x x g b c x f m mk--=. 记)()()(112x f x x g b c x f m mk--=，且))(())((12x f x f ∂≤∂故))(),(())(),((21x f x f x g x f = 如此下去，所得差式的次数不断降低，即 ≥∂≥∂≥∂))(())(())((21x f x f x g .因此在有限次之后，必然有一差式为零，即)0),(())(),(())(),((21x f x f x f x g x f r === ，则)(x f r 乘以首项系数的倒数之后即为)(x d .例1 例1 设x x x g x x x f +=-=23)(,)(求)(f(x),g(x). 解：由题意得：用等式表示出来，就是)66)(3161()()23)(3()(2++=++-=x x x g x x x x f 因此1))(),((+=x x g x f例 2 设1256)(,22)(23234-++=--+=x x x x g x x x x x f 求))(),((x g x f ，并求)(),(x v x u 使)()()()())(),((x g x v x f x u x g x f +=.解：由题意得：用等式表示即)482018()()4()(2-++-=x x x g x x f)9494()482018)(5413181()(2++-++=x x x x x g)108281)(9494(4820182++=-+x x x x 因此1))(),((-=x x g x f 而)482018)(5413181()(94942-++-=-x x x x g x )]()4()()[5413181()(x g x x f x x g --+-=)()]4)(5413181(1[)()5413181(x g x x x f x -+++--= )()271541181()()5413181(2x g x x x f x +++--= 于是，令271541181)(,5413181)(2++=--=x x x v x x u 就有)()()()())(),((x g x v x f x u x g x f +=方法2：方程组法求解多项式的最大公因式定理 4 设)(x f 、)(x g 是][x P 上的两个多项式，令⎩⎨⎧==0)(0)(x g x f 将方程组化解为⎩⎨⎧==0)(c x d 则当0=c 时，][x P 中多项式)(x d 是)(x f 与)(x g 的最大公因式；当0≠c 时，)(x f 与)(x g 互素.（其中c 是常数）例 3 设22)(,623)(2323-+-=+++=x x x x g x x x x f 求))(),((x g x f解：作方程组⎩⎨⎧=-+-=+++02206232323x x x x x x ⎩⎨⎧=-+-=+−−−→−÷-022022324))2()1((x x x x ⎩⎨⎧=--=+−−−→−⨯+020222)1()2(x x x⎩⎨⎧==+−−→−+00022)1()2(x所以2))(),((2+=x x g x f例 4 设22)(,242)(234234+-+-=+-+-=x x x x x g x x x x x f 求))(),((x g x f解：作方程组⎩⎨⎧=+-+-=+-+-0220242234234x x x x x x x x ⎩⎨⎧=+-+-=--−−→−-022022343)2()1(x x x x x x ⎩⎨⎧=+---=--−−−→−⨯+02202233)1()2(x x x x x x⎩⎨⎧=-=--−−→−-020223)2()1(x x x⎩⎨⎧=-=−−−→−⨯-02002)2()1(x x所以2))(),((2-=x x g x f。

辗转相除法求最大公因数辗转相除法，又名欧几里德算法，是求两个正整数之最大公因数的算法。

辗转相除法最大的用途就是用来求两个比较大的数的最大公因数。

如：求83613和121824的最大公因数。

一、辗转相除法定理的证明用（a,b）来表示a和b的最大公因数。

有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。

证明：由于a=b+c 于是有c=a-b那么如果有d|a，且d|b，就必然有d|a-b，也就是d|c，可见a和b的公因数必然也是c的因数。

现在假设d是a,b的最大公因数，那么d也必然是c的因数，于是d是b,c的公因数，现在就要证明它是最大公因数——因为a=b+c，于是b,c的公因数也必然是a的因数，假设(b,c)=e，（由“d是b,c的公因数”知道d|e）那么有e|b+c，即e|a，可见e也是a,b的公因数，e|d,综上有e=d可见(a,b)=(b,c)=d这个思想一推广，就成了辗转相除法了。

二、例题求15750 与27216的最大公约数。

解：∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）∵2898=1386×2+126 ∴（2898，1386）=（1386，126）∵1386=126×11 ∴（1386，126）=126所以（15750，27216）=216三、练习求8251和6105的最大公因数。

求83613和121824的最大公因数。

两个多项式互素辗转相除法以两个多项式互素辗转相除法为主题，我们先来了解一下什么是多项式和互素。

多项式是由若干个单项式相加（减）而成的代数式，其中每个单项式的系数都是常数，而指数可以是任意非负整数。

比如，3x² - 2x + 1就是一个多项式。

互素是指两个或多个整数（或多项式）的最大公因数（或最大公因式）为1。

也就是说，两个多项式如果没有公共的因式，就称它们为互素。

那么，两个多项式互素辗转相除法又是什么呢？两个多项式互素辗转相除法，又称为欧几里得算法，是一种求解两个多项式的最大公因式的方法。

它的基本思想是通过一系列除法运算，不断将两个多项式转化为除数和余数的形式，直到余数为0为止。

最后，最后一个非零余数就是两个多项式的最大公因式。

具体来说，我们可以将两个多项式按照次数从高到低排列，然后进行除法运算。

首先，将次数较高的多项式作为被除数，次数较低的多项式作为除数，进行一次除法运算。

然后，将上一步的除数作为被除数，上一步的余数作为除数，进行下一次除法运算，直到余数为0。

最后一个非零余数就是两个多项式的最大公因式。

下面，我们通过一个例子来说明两个多项式互素辗转相除法的具体步骤。

假设我们要求解多项式f(x) = 2x³ - 3x² + 4x - 5和g(x) = x² - 2x + 1的最大公因式。

按照次数从高到低排列两个多项式，得到f(x) = 2x³ - 3x² + 4x - 5和g(x) = x² - 2x + 1。

然后，将较高次数的多项式f(x) = 2x³ - 3x² + 4x - 5作为被除数，较低次数的多项式g(x) = x² - 2x + 1作为除数进行一次除法运算。

2x³ - 3x² + 4x - 5 ÷ x² - 2x + 1 = 2x - 1得到商式为2x - 1，余数为0。

辗转相除法求最大公因数的原理
辗转相除法求最大公因数的原理
一、辗转相除法可以求两个因数的最大公因数。

（欧几里德算法）
1.我们可以用列举法、筛选法及短除法求得，如：6和9的最大公因数（6，9）=3
2.辗转相除法。

9÷6=1 (3)
6÷3=2
3就是9和6的最大公因数。

再如：30和80的最大公因数。

80÷30=2 (20)
30÷20=1 (10)
20÷10=2
10就是30和80的最大公因数。

辗转相除法优点是可以求出两个大数的最大公因数
二、辗转相除法求最大公因数的原理
如果我们要求8251与6105的最大公因数的话，假设8251是这个数x的a倍，再假设6 105是x的b倍，那么2146=8251-6105，是x的(a-b)倍，也是x的倍数，而无论这几个数如何加减，甚至相乘，都还是最大公约数的倍数，我们就可以把求8251与6105的最大公约数简化成求2146和6105的最大公约数，再把求2146与6105的最大公约数简化为求3959(=6105-2146)与2146的最大公约数，如此相减往复几次后，会发现两个数变相等了37=37，这个数就是两个原来数的最大公因数。

举个例子9和69-6=3，保留6,36-3= 3，保留3,3发现两数相等，为3所以最大公因数为3
9和6的最大公因数，我们知道是3。

9是3的倍数，6是3的倍数，那3也一定是3的倍数。

30和80的公因数为m，30是m的倍数，80是m的倍数。

80里有的两个30也肯定是m的倍数，剩下的20也会是m倍数。

10也会是m的倍数。

10=10=m。

多元多项式怎么用辗转相除法求最大公因子多元多项式是指含有多个变量的多项式，其求最大公因子的方法与单变量多项式相似，可以通过辗转相除法进行求解。

具体步骤如下： 1. 将多元多项式表示为单变量多项式的形式。

例如，对于含有
两个变量x和y的多项式f(x,y)，可以将其表示为f(x,y)= g(x)*h(y)，其中g(x)和h(y)分别为f(x,y)关于x和y的单变量多项式。

2. 对g(x)和h(y)分别使用单变量多项式辗转相除法求出它们
的最大公因子s(x)和t(y)。

3. 将s(x)和t(y)表示为多元多项式的形式，即s(x,y)和t(x,y)。

4. 最大公因子为s(x,y)*t(x,y)。

需要注意的是，在进行多元多项式辗转相除法时，需要使用多元多项式的除法规则，即首先对多项式中的第一个变量进行除法，然后对所得的余项再对第二个变量进行除法，以此类推，直至得到最终的余项为零。

- 1 -。

目录一引言 (1)1.1 背景 (1)1.2 研究现状 (1)1.3目的 (1)二问题的提出 (1)三问题的解决 (5)3.1 矩阵法 (5)3.2矩阵初等行（列）初等变换法 (8)3.3 数值矩阵法 (12)四问题的总结 (15)致谢 (17)参考文献 (18)一元多项式最大公因式的求法及比较摘要 设P 是一个数域，[]X P 为数域P 上的一元多项式环，多项式()x d 是多项式()()x g x f ,的一个最大公因式，那么存在[]X P 中的多项式()()x v x u ,使得()()()()()x g x v x f x u x d += （1）成立.采用因式分解法和辗转相除法可求得最大公因式.然而并不是所有的一元多项式都能因式分解，在辗转相除的过程中不能用一个非零的常数去乘以除式及被除式，增加了运算困难，并且当()()x g x f ,次数较高时，运用辗转相法时显得十分麻烦. 本文中，在因式分解法和辗转相除法两种方法的基础上，我们给出更简便的求解最大公因式的方法，并通过相应数值例子对各种方法进行比较分析.关键词 最大公因式；公因式；多项式；矩阵初等变换 中国分类号：o 151The methods of finding the greatest common factors for polynomials of one indeterminate and comparisonsLUO Jiaojiao(School of Mathematics and Statistics, Tianshui Normal University, 741000)Abstract: Let P[x] be a polynomial ring on numerical field P. Suppose that ()x d is a polynomial greatest common factor of )xf, theng(x),(()()()()()x g x vd+x= . (1)fuxxWe can obtain the greatest common factor by using factorization method of factor and the flounder division, but it is always not efficient for the polynomial with large sizes In particular, the divisior may not be a non-zero constant, which increase the computing difficulties. In this paper, we propose some simpler approachs to find the greatest common factor. These methods are compared by numerical examples.Key words: Greatest common factor; common factor; polynomial;Matrix transpose一元多项式最大公因式的求法及比较一 引言 1.1 背景最大公因式的概念是多项式代数的重要内容，关于最大公因式的求法一般只讨论两个多项式的最大公因式的求法，方法主要有因式分解法和辗转相除法.考虑n 个多项式的最大公因式时，往往也是通过两两多项式求最大公因式，因此求多个多项式的最大公因式需要多次对两个多项式进行运算.为了改进方法逐渐出现了矩阵初等变换法等利用多项式矩阵和数字矩阵的运算来求解最大公因式，虽然不尽完善，但也是一种很大的突破.本文将在此基础之上对求最大公因式的方法进一步作一个较全面的探讨（包括理论研究和实例说明），最后对各种方法的优劣性进行综述.1.2 研究现状文献[]3对因式分解法和辗转相除法作了简要介绍；利用矩阵来求解最大公因式的方法在文献[][][]6,5,4[]7,中都有所体现.1.3 本文研究的问题通过对各种求最大公因式的方法的探讨和比较能够灵活合理利用矩阵（多项式矩阵或数值矩阵）的相关性质去求n 个多项式的最大公因式.二 问题的提出在高等教材[]1中，有如下定义和定理：定义1 如果多项式()x ϕ既是()x f 的因式，又是()x g 的因式，那么()x ϕ就称为()x f 与()x g 的一个公因式.定义2 设()x f ，()x g 是[]x P 中两个多项式. []x P 中多项式()x d 称为()x f ，()x g 的一个最大公因式，如果它满足下面两个条件：1）()x d 是()x f ，()x g 的公因式； 2）()x f ，()x g 的公因式全是()x d 的因式.定理1 对于[]x P 中任意两个多项式()x f ，()x g ，在[]x P 中存在一个最大公因式()x d ，且()x d 可以表成()x f ，()x g 的一个组合，即有[]x P 中多项式()x u ,()x v 使()()()()()x g x v x f x u x d +=. ① 证明 如果()x f ，()x g 有一个为零，譬如说，()0=x g ，那么()x f 就是一个最大公因式，且()()011⋅+⋅=x f x f .下面来看一般的情形.无妨设()0≠x g .按带余除法,用()x g 除()x f ,得到商()x q 1,余式()x r 1;如果()01≠x r ,就再用()x r 1除()x g ,得到商()x q 2,余式()x r 2;又如果()02≠x r ,就用()x r 2除()x r 1,得出商()x q 3,余式()x r 3;如此辗转相除下去,显然,所得余式的次数不断降低,即()()()()()() >∂>∂>∂x r x r x g 21因此在一有限次之后，必然有余式为零，于是我们有一串等式；()()()()x r x g x q x f 11+=， ()()()()x r x r x q x g 212+=，…………()()()()x r x r x q x r i i i i +=--12,…………()()()()x r x r x q x r s s s s 1213----+=, ()()()()x r x r x q x r s s s s +=--12, ()()()011+=+-x r x q x r s s s .()x r s 与0的最大公因式是()x r s .根据前面的说明，()x r s 也就是()x r s 与()x r s 1-的一个最大公因式；同样的理由，逐步推上去，()x r s 就是()x f 与()x g 的一个最大公因式.由上面的倒数第二个等式，我们有()()()().12x r x q x r x r s s s s ---=再由倒数第三式，()()()(),2131x r x q x r x r s s s s -----=代入上式可消去(),1x r s -得到()()()()()()().1321x r x q x r x q x q x r s s s s s s ----+=然后根据同样的方法用它上面的等式逐个消去，再并项就得到这就是定理的①式. 证毕由最大公因式的定义不难看出，如果()()x d x d 21,是()x f 与()x g 的两个最大公因式，那么一定有()()x d x d 21|与()()x d x d 12|，也就是()()x cd x d 21=，0≠c .这就是说，两个多项式的最大公因式在可以相差一个非零的常数倍的意义下是唯一确定的.我们知道，两个不全为零的多项式的最大公因式总是一个非零多项式.在这个情形，我们约定，用()()()x g x f ,来表示首项系数为1的那个最大公因式.由定义1和定义2我们很容易得到一种求多项式的最大公因式的方法—因式分解法.由定理1的证明过程我们找到另一种求多项式的最大公因式的方法—辗转相除法.例1 求()x f 与()x g 的最大公因式：()().1,14323234--+=---+=x x x x g x x x x x f 解 用辗转相除法，得用等式写出来就是()()()()()()132211---+=+=x x x xg x r x g x q x f()()()()()⎪⎭⎫ ⎝⎛--+⎪⎭⎫ ⎝⎛+-=+=434341211212x x r x x r x r x q x g()()()()x r x x r x q x r 22313438⎪⎭⎫ ⎝⎛+==故 ()()()1,+=x x g x f而 ()()()()x r x q x g x x r 1224343-=--=()()()()()()x g x q x f x q x g 12--= ()()()()()()x g x q x q x f x q 2121++-= 于是，令()()()()()().134,34212x q x q x v x q x u +-==就有 ()()()()()()()().,x g x v x f x u x g x f x d +==对于因式分解法，我们知道并不是所有的一元多项式都能因式分解，即使可以因式分解但分解的过程往往比较困难，故此方法并不理想.对于辗转相除法，求得()x d 后再利用逐步代入法求得()()x v x u ,使得（1）式成立，但是当()()x g x f ,次数较高时，运用辗转相法时显得十分麻烦. 特别，在辗转相除的过程中不能用一个非零的常数去乘以除式及被除式，增加了运算困难.于是我们提出这样的问题：如何利用定义和定理，寻找到一种比较简便可行的方法来求n 个多项式的最大公因式并找出()()n i x u i ,,2,1 =，从而把()x d 表示成()()n i x f i ,,2,1 =的一个组合，使得()()().1∑==ni i i x f x u x d三 问题的解决 3.1 矩阵法1. 求两个多项式的最大公因式[]2令21,f f 是两个多项式，不妨设21f f ∂≤∂，用1f 去除2f 有121212r g f f +=，f r ∂<∂12，即()()1211221101r f g f f =⎥⎦⎤⎢⎣⎡-.设⎥⎦⎤⎢⎣⎡-=101121g A 可知1A 是可逆阵，再用12r 去除1f 有2121121r g r f +=，1221r r ∂<∂，即()()122121121101r r g r f =⎥⎦⎤⎢⎣⎡-.设⎥⎦⎤⎢⎣⎡-=101122g A ，则2A 也是可逆阵，依次做下去，由于}{ij r ∂在绝对递减，必有某时有()()2210k k k r r r =或()01k r .不妨设01≠=d r k ，02=k r ，则()()02121d A A A f f s = .()()02d A f f=，其中s A A A A 21=是可逆阵.设A 的第一列为21,u u ，则有d u f u f =+2211. ②又由于()()1210-=A d f f ，21,f f 均可由d 表示，即d 是21,f f 的公因式.综合②得d 是21,f f 的最大公因式.例2 ,9516242341++--=x x x x f .452232+--=x x x f 求1f 与2f 的最大公因式d ，并求使d u f u f =+2211的.,21u u解 ,12f f ∂<∂作除法()()9362221+--+=x x x f f ，即()().93612012221f x x x f f +--=⎥⎦⎤⎢⎣⎡-再作除法，(),313193622⎪⎭⎫⎝⎛+-+--=x x x f即 ()().19361031311936222+-+--=⎥⎥⎦⎤⎢⎢⎣⎡-+--x x x x f x x 再作除法， ()(),09619362+++-=+--x x x x即 ()().101960119362+-=⎥⎦⎤⎢⎣⎡--+-+--x x x x x 则 ()1+-=x x d 且()(),10196011031311120121+-=⎥⎦⎤⎢⎣⎡--⎥⎥⎦⎤⎢⎢⎣⎡-⎥⎦⎤⎢⎣⎡-x x x x f f ().32231313119601103131112012⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--*-*=⎥⎦⎤⎢⎣⎡--⎥⎥⎦⎤⎢⎢⎣⎡-⎥⎦⎤⎢⎣⎡-=x x x x x x A 由于d 在第2列，所以A 的第2列即是21,u u .()32231,3131221--=-=x x u x u ，使d u f u f =+2211. 注：通常要求为首一多项式，这只需将上述的除以的首项系数即可. 2. 求3个多项式的最大公因式321,,f f f 是3个多项式，{}3211,,m inf f f f ∂∂∂=∂，用1f 去除32,f f ，有131313121212,rg f f r g f f +=+=, 即 ()(),1000101131211312321r r f g g f f f =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=100010113121g g A .不妨设{}1312112min r r f r ∂∂∂=∂，再用12r 去除1f 和13r ，有 232312132121121,r g r r r g r f +=+=，即()()⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--==⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--1001001,100100123212231221232113121g g A r r r g g r r f .继续作下去，由于{}ij r ∂绝对递减，必有某时321,,k k k r r r 中有一个不为零，其余全为零.不妨设,0321==≠=k k k r r d r ，则有()()0021321d A A A f f f s = ，记()均可逆S S A A A A A A A ,,,2121 =，则有()()00321d A f f f =.设A 的第一列为,,,321u u u 则d u f u f u f =++332211.又()()132100-=A d f f f ，即321,,f f f 均可由d 表示，即d 是321,,f f f 的公因式.故d 是最大公因式.例 3 .12,452,951624232322341+-=+--=++--=x x f x x x f x x x x f 求321,,f f f 的最大公因式，并求321,,u u u 使d u f u f u f =++332211.解 3f ∂最小，用3f 去除21,f f ，有()()()(),132,171786432231+-++=+-+-+=x x f f x x x f f 即()()()1,1171713286401000132321+-∂+-+-=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--+--x f x x x x x f f f 最小，再作除法，()()()().011,017117173++-+-=++-=+-x x f x x 即 ()()().0101001117001117173+-=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡+---+-+-x x f x x 1+-=x d 是最大公因式.().321010011170011328640100012⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡*--*****=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡+---⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--+--=x x x x x A 取32,1,0321--===x u u u ，有d u f u f u f =++332211.3. 求n 个多项式的最大公因式n f f f ,,21是n 个多项式，{},,,min 211n f f f f ∂∂∂=∂ 用1f 去除,,2n f f 有,,,,111131313121212n n n r g f f r g f f r g f f +=+=+=即()().1000101112111221n n n r r f g g f f f=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--设⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=10001011121 n g g A （必是可逆阵） 不妨设()n r r f r 113112,,,min ∂∂∂=∂ ，再用12r 去除n r r f 1131,, 有⎪⎪⎩⎪⎪⎨⎧+=+=+=,22121232312132121121nn n r g r r r g r r r g r f 即()().1001001212212211121n n n r r r g g r r f =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--设⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=10010012212 n g g A （必是可逆阵）.继续下去，由于{}ij r ∂绝对递减，必有某时()in i r r ,,1 中只有一个不为零其余全为零.不妨设01≠=d r i ，则()()00121 d A A f f f S n =.设s A A A A 21=是可逆阵，()()0021d A f f f n =，设A 的第一列为n u u u ,,,21 ，有d u f u f u f n n =+++ 2211，且()(),00121-=A d f f f n ∴,1f ,2fn f , 均可由d 表示，即d 是,1f ,2f n f , 的公因式.故d 是最大公因式.3.2 矩阵的初等行（列）变换法在这里我们以初等列变换法为例（初等行变换法原理一样）定理2[]1 设()[],,,2,1,s i x P x f i =∈则()()()()()()()()()()x f x f x f x f x f x f x f s s s ,,,,,,,12121-=定理3[]3 把[]x P 中任意n 个多项式写成n ⨯1矩阵形式()()()()x f x f x f n ,,,21 ，存在n 阶方阵()[]()x P Mn x R ∈，使得()()()()x f x f x f n ,,,21 ()()()0,,0, x d x R =其中，()x d 是()()()x f x f x f n ,,,21 的最大公因式.证明 对于()()x f x f 21,存在最大公因式：(),1x d 且存在()()[],,11x P x v x u ∈使得：()()()()()x d x v x f x u x f 11211=+ 令()⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡-=1111211 f v f u x R 于是有()()()()()()()()()x f x f x d x R x f x f x f n n ,,,0,,,,31121 =，对于()(),,13x d x f 存在最大公因式()x d 2且存在()()x v x u 22,使得：()()()()().22321x d x v x f x u x d =+ 令：()⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-=11112322 d vf u x R .于是有()()()()()()()()()x f x f x d x R x f x f x d n n ,,,0,0,,,,0,42231 =如此继续下去，将得到()()()()()()()()().0,,0,0,,,,112121 x d x R x R x R x f x f x f n n n --=又由定理2可知：()()()()()()()()()x f x f x d x f x f x f x d n n ,,,,,,3121 ==()()()()()()x d x f x f x d n n 142,,,-===故 ()()()()()()()()().0,,0,0,,,,12121 x d x R x R x R x f x f x f n n n =- 这里只要令 ()()()()x R x R x R x R n 121-= 定理得证. 证毕定理4 对于定理2中的()x R ，可以表示成有限个初等矩阵的乘积形式. 证明 不妨对()x R 1进行证明()()()()−−−→−⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡-−−→−⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡-=+12111211111211211111f f f v f f f u f v f u x R ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡111111111111111f v d f v d 这个初等变换的过程可以写成：()()()()()()()()()()(),21,2112,1121112f P v P d P x R f P f P =即：()()()()()()()()()()().21,212,1112121111f P v P d P f P f P x R --=对于其它(),x R k 都可以表示成初等矩阵的乘积形式，所以()x R 可以表示成初等矩阵的乘积形式.注：()()()()()k j i P c i P j i P ,,,,分别表示矩阵的三种初等变换[]3； ()()111f P -是形式表达式并不会出现()x f 1的倒数形式. 定理5 设()()()()n n x f x f x f A ⨯=121,,, 是[]x P 上的非零阵，()=x d()()()()x f x f x f n ,,,21 ，n I 是n 阶单位矩阵，()()n x d B ⨯=10,,0, ，()x R 为定理2中的()x R ，则矩阵⎪⎪⎭⎫ ⎝⎛n I A ，经过一系列初等列变换可化为()⎪⎪⎭⎫⎝⎛x R B ，而()x R 的第一列元素就是()()n i x u i ,,2,1 =，使得()()()()()()()x d x u x f x u x f x u x f n n =+++ 2211成立.证明 ()()()()n n x f x f x f A ⨯=121,,, 是[]x P 上的非零阵，()=x d ()()()()x f x f x f n ,,,21∴ 由定理3知，存在[]x P 上的n 阶可逆阵()x R ，使得()()()n x d x AR ⨯=10,,0, ，于是在⎪⎪⎭⎫⎝⎛n I A 的右边乘上()x R ，则有⎪⎪⎭⎫ ⎝⎛n I A ()x R ()()()⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛=x R B x R x AR ，且()x R 的第一列元素就是()()n i x u i ,,2,1 =，使得：()()()()()()()x d x u x f x u x f x u x f n n =+++ 2211成立. 证毕例4 对于整系数多项式()()().632;2;25323432322x x x x x f x x x x f x x x f +++=+-+=-+=求它们的最大公因式()x d ；且求：()()3,2,1=i x u i 使得()()()()()()()x d x u x f x u x f x u x f =++332211成立.解 令 ⎪⎪⎪⎪⎪⎭⎫⎝⎛=100010001321f f f C 对其进行如下的的行初等变换： ⎪⎪⎪⎪⎪⎭⎫⎝⎛=100010001321f f f C ()−−→−⎪⎪⎪⎪⎪⎭⎫⎝⎛---+−−−−→−+-+--13122132121001210001232x x x f f x ()−−−−→−⎪⎪⎪⎪⎪⎭⎫⎝⎛----++-+----++−−−−−→−⎪⎪⎪⎪⎪⎭⎫⎝⎛---+-+++++-+-231,1322211,112222311361212211222101121120012322x x x x x x x x x x x x x x x x f x x[],1323162523612120023213362521621122100223,122⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-+-+-----++---+−→−⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-+-+---+----+-+x x x x x x x x x x x x x x x x x x x x ()⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-+-+-----++---=13231625236121222x x x x x x x x x x R 其中，(),2+=x x d ()()().3,36,2321-=+==x u x x u x u经验证 ()()()()()()()x d x u x f x u x f x u x f =++332211成立.注：进行初等变换的目的是要把C 的第一行变成()()00 x d 形式，在作初等列变换过程中，系数保持是整数，在这个原则下可以随意地作初等列变换，得到的()x d 是唯一的.但由于作法不同，得到的()x R 的第一列元素()()n i x u i ,,2,1 =可能不同，故线性表示不唯一，但都能使()()()()()()()x d x u x f x u x f x u x f =++332211成立.3.3 数值矩阵法我们在前面介绍了矩阵的初等变换法，其实质是利用多项式矩阵的初等行（列）变换求多项式矩阵的一阶行列式因子，并且，在求解的过程中，仍然是多项式的运算，有一定的难度.下面我们利用多项式的某些性质建立一种利用数值矩阵的行初等变换求解多个多项式最大公因式的方法—矩阵数值法.该方法摆脱了求解过程中的多项式运算，而单纯运用数值矩阵的初等行变换，直观明了，简单易行.设一元n 次多项式(),110n i n i n n a x a x a x a x f +++++=-- 其性质由其系数唯一决定.即它和由其系数所形成的行矩阵()n a a a 10一一对应.对于m 个一元多项式()()m i a x a x a x f n i n i n i i ,,2,11,121 =+++=+- ③若③中至少有一个多项式的次数是n 次，在不计次序的情况下，它与其系数所形成的矩阵也是一一对应的.其系数矩阵为()11,211,222211,11211+⨯+++⎪⎪⎪⎪⎪⎭⎫⎝⎛=n m n m m m n n a a a a a a a a a A ④而最大公因式与次序无关，所以③的最大公因式由A 唯一决定.定理6[]1 若()()()()()(),,,11bc ad x dg x cf x g x bg x af x f ≠+=+=则()()()()()().,,11x g x f x g x f =由定理6：当1,0,1===d b a 时，有()()()()()()()x g x cf x f x g x f +=,,； 当1,0,1===d c a 时，有()()()()()()()x g x bg x f x g x f ,,+=； 当1,0,0,0===≠d c b a 时，有()()()()()()x g x af x g x f ,,=.又有()()()()()()x f x g x g x f ,,=.所以对④实施初等行变换后，其所对应的多项式组与③有相同的最大公因式.定理7[]4 设()()(),,1111m n x b x b x b x g x a x a x a x f l l m m m m k k n n n n >+++=+++=---- l k m n b a b a ,,,均不为零，则⑴当l k >，有()()()()()⎪⎭⎫⎝⎛=-x g x f x x g x f l k ,1,；当l k <，有()()()()()⎪⎭⎫⎝⎛=-x g x x f x g x f k l 1,,；⑵当l k =时，有()()()()()()x g x x f x g x f m n -=,,.证明 当l k >时，令()()()()()x g x x g x f x x x f x x f l l k l l 121,===-，其中()(),,112111k k n n k n n l k k l n n l n n a x a x a x f x a x a x a x f +++=+++=--------- ().111l l m m l m m b x b x b x g +++=----而()l k l k n n l k n n lk x a x a x a x f x+++=+---+-- 111，则有()()()()()()()()()()()()x g x f x x x g x f x x g x x f x x g x f l k l l l l ,,,,21111-=== ⑤因为()()1,1=-x g x l k ，故⑤()()()()().,1,12⎪⎭⎫⎝⎛==-x g x f x x g x x f x l k l l当l k =时，此时()()x f x f 21=，有()()()()()()x g x f x x g x f l 11,,=，因为()()1,1=-x f xmn ，有()()()()()()()()()()()().,,,,111111x g x x f x g x x x f x x g x x f x x g x f x m n m n l l m n l l ---===证毕也就是说，对于④中的任意两行，l i k i a a 211,分别时所在行中列数最大的非零元素，2211,j i j i a a 分别是所在行中列数最小的非零元素.有如下结论：⑴若l k ≠，不妨假设l k >，则第2i 行的非零元素向右平移()l k -个列（下面将该过程简称右对齐）后，其所对应的多项式组与③有相同的最大公因式；⑵若l k =，而21j j >时，则第1i 行的非零元素向左平移()21j j -个列（下面将该过程简称左对齐）后，其所对应的多项式组与③有相同的最大公因式.另外，由()()()()()()01,,0,≠==k k x f x f x f ，可知去掉④中的所有元素都为0的行后其所对应的多项式组与③有相同的最大公因式；若出现()()000≠k k 行，则③的最大公因式为1.定理8 利用以上性质一定能将④变成()11+⨯n 型矩阵.该矩阵对应的多项式即为③的最大公因式.利用以上结论，就可以利用矩阵的初等行变换求出一元多项式组的最大公因式，其一般步骤为：㈠ 将系数矩阵A 利用初等行变换化为阶梯矩阵B .㈡ 考察矩阵B ，若出现元素都是0的行，则去掉该行；若某行变为()()000≠k k 时，多项式的最大公因式为1，计算终止；若出现每一行的列数最大的非零元素不在同一列时，则施行右对齐；若每一行的列数最大的非零元素在同一列时，则施行左对齐；将B 变成非阶梯矩阵，然后，以非零元素最少的行将其再化成阶梯矩阵.㈢ 反复循环上述步骤，直到A 变为()11+⨯n 型矩阵，则对应的多项式即是③的最大公因式.例5 设 ()()().22;64;34242332322341+--=++-=-++-=x x x x f x x x x f x x x x x f 求321,,f f f 的最大公因式.解 系数矩阵⎪⎪⎪⎭⎫⎝⎛-----−−→−⎪⎪⎪⎭⎫ ⎝⎛-----→⎪⎪⎪⎭⎫ ⎝⎛-----=004220614134241422006141034241212106141034241左对齐A ()1100011000000001100022000011002200001100211001100021100110000000021100321006330021100321000633000211344300633000211342410614100211→⎪⎪⎭⎫ ⎝⎛--→⎪⎪⎭⎫⎝⎛----−−→−⎪⎪⎭⎫⎝⎛----→⎪⎪⎭⎫ ⎝⎛----−−→−⎪⎪⎭⎫⎝⎛----→⎪⎪⎪⎭⎫⎝⎛----→⎪⎪⎪⎭⎫ ⎝⎛-----−−→−⎪⎪⎪⎭⎫⎝⎛-----→⎪⎪⎪⎭⎫⎝⎛-----→⎪⎪⎪⎭⎫ ⎝⎛-----→右对齐左对齐右对齐所以，最大公因式为1+x .四 问题的总结我们已经对求解多项式的最大公因式的问题给出了5种可行方法，各方法各有优缺点，现我们总结如下：因此，我们可以依照以上的对比结果根据多项式的表达式特征、多项式的个数以及是否需要得到最大公因式的线性表达等情况的不同灵活选择不同的方法来求最大公因式.致谢通过完成此次毕业论文，我深切体会到知识是无穷无尽的，需要我们去不断探索，不断发现.同时，我学会了一种探索新知识的方法：从最基本的最简单的定义出发，通过分析原理，结合其它相关知识，更换角度思考问题，通过实际举例进一步使理论具体化同时也体现理论的可实用性.能比较顺利的完成此次论文首先需要感谢的是我的论文指导老师：梁老师.从第一次选题到第二次选题再到确定研究课题；从论文的格式到论文的布局再到较好的完成论文所需要的注意事项；从整体到局部从宏观到细节.梁老师都积极支持我的想法，给予我很多好的建议，在这里，要真心感谢梁老师给予我的帮助.另外，还要感谢和我一起讨论问题给我建议的同学们，谢谢他们给我的鼓励.数学与统计学院2009届毕业论文参考文献[1] 北京大学数学系编.高等代数（第三版）.北京：高等教育出版社.[2] 蔡若松. 求几个多项式的最大公因式. 锦州师范学院学报（自然科学版）, 1998.3.[3] 陈辉，陈凌云. 多项式最大公因式的一种求法. 杭州师范学院学报, 2000.06.[4] 刘国琪. 多项式的最大公因式的一种新求法. 河北电力职工大学，工科数学,1997.04.[5] T.W.Hungerford. 冯克勤译. 代数学[M]. 长沙:湖南教育出版社, 1984.[6] 李正彪, 李祥. 求多项式最大公因式的一种新方法. 曲靖师范学院学报, 2004.11.[7] Nathan Jacobson..Basic Algebral[M].San.Francisco:W.H.Freeman and company,1980.19。