2.3  最大公因式

2.3 最大公因式

定义2.2 若f（x）和g（x）是数域F上的多项式，如果数域F上的多项式d（x）满足条件：

（1）d（x）|f（x）且d（x）|g（x）；

（2）如果h（x）|f（x）且h（x）|g（x），则h（x）|d（x），则称d（x）是f（x）和g（x）的最大公因式.显然，最大公因式并不是唯一的，因为若d（x）是最大公因式的话，那么它的任何非零倍数同样也是.通常，把首项系数为1的最大公因式记作（f（x），g（x））.

例2.7 设多项式

f（x）=（2x-1）（x-1）（3x+2），g（x）=（2x-1）（x-1）（2x+1），容易看到，2x-1，x-1都是f（x）和g（x）的公因式，2x²-3x+1是f（x）和g（x）的一个最大公因式，且

引理2.1 若f（x）=q（x）g（x）+r（x），则（f（x），g（x））=（g（x），r（x）），这里，f（x），g（x），q（x），r（x）都是数域F上的多项式.

证明：记

d₁（x）=（f（x），g（x）），d₂（x）=（g（x），r（x）），

则有d₁（x）|f（x）且d₁（x）|g（x），因此，d₁（x）|r（x），由最大公因式的定义

d₁（x）|d₂（x）.

同理，d₂（x）|d₁（x）.再由它们都是首一多项式，得d₁（x）=d₂（x）.证毕.

由定理2.1及引理2.1可见，如果多项式f（x）除以g（x）的余式是r（x），则f（x）和g（x）的最大公因式就是g（x）和r（x）的最大公因式.这样计算f（x）和g（x）的最大公因式的问题就变为计算g（x）和r（x）的最大公因式的问题，而r（x）的次数不大于f（x）的次数，因而问题得到简化.再注意到如果余式r（x）=0，则g（x）就是f（x）和g（x）的一个最大公因式.

对于两个非零多项式f（x）和g（x），用f（x）除以g（x），设商为q₁（x），余式为r₁（x）.如果r₁（x）=0，则最大公因式已经可以求得.否则，用g（x）除以r₁（x），如果余式仍然不是零，则用上一次的除式除以余式，反复这样的过程可以得到下列等式：

由于余式r_i（x）的次数是严格下降的，因此，上面所叙述的过程一定是可以终止的.由前面的分析，可以看到

（f（x），g（x））=（g（x），r₁（x））=（r₁（x），r₂（x））=…=（r_s-1（x），r_s（x））=ar_s（x），

其中ar_s（x）是f（x）和g（x）的最大公因式，且是由它们唯一确定的首一多项式.

上述这组等式通过简单的移项，我们可以得到下面一组等式

把r_s-1（x），r_s-2（x），…，r1（x）依次代入最后一式，可得r_s（x）=u（x）f（x）+v（x）g（x）.

上面这种求最大公因式的方法称为辗转相除法，在西方则以Euclid（公元前330—公元前275）算法而著称.这样我们就可以得到如下定理.

定理2.2 若f（x）和g（x）是数域F上不全为零的多项式，则它们的最大公因式一定存在，并且在不计常数倍的情况下是唯一的.若d（x）是f（x）和g（x）的最大公因式，则存在数域F上的多项式u（x）和v（x），使得

d（x）=u（x）f（x）+v（x）g（x）.

例2.8 利用辗转相除法求多项式

f（x）=x⁴-x³+x²+x-2

和

g（x）=x³-1

的最大公因式，并求一组多项式u（x），v（x）使得

u（x）f（x）+v（x）g（x）=（f（x），g（x））.

解：由多项式f（x）=x⁴-x³+x²+x-2和g（x）=x³-1，利用多项式的带余除法得到

f（x）=（x-1）g（x）+x²+2x-3， q₁（x）=x-1，r₁（x）=x²+2x-3；

g（x）=（x-2）r₁（x）+7x-7， q₂（x）=x-2，r₂（x）=7x-7；

所以，

从前面的计算过程有

r₂（x）=g（x）-（x-2）r₁（x）， （2.11）

r₁（x）=f（x）-（x-1）g（x）. （2.12）

把式（2.12）代入式（2.11）得到

r₂（x）=g（x）-（x-2）[f（x）-（x-1）g（x）]

=-（x-2）f（x）+（x²-3x+3）g（x）.

取多项式u₀（x）=-x+2，v₀（x）=x²-3x+3，则有

u₀（x）f（x）+v₀（x）g（x）=r₂（x），

再令多项式

则可以得到f（x）与g（x）的最大公因式

辗转相除法是做一系列多项式除法运算，因此我们也可以借助竖式进行计算.我们可以把算式（2.10）排列成如下的竖式格式.

这里的竖式算法还可以使用分离系数法进行，这样书写会更加简洁.

例2.9 利用分离系数法计算下列两组多项式的最大公因式.

（1）f（x）=3x⁴-5x³+4x²+1，

g（x）=3x³-2x²+x-1；

（2）f（x）=x⁵+5x⁴+9x³+7x²+5x+3，

g（x）=x⁴+2x³+2x²+x+1.

解：（1）利用分离系数法有如下竖式：

因此，（f（x），g（x））=1.

（2）利用分离系数法有如下竖式：

因此，（f（x），g（x））=1.

定义2.3 若f（x）和g（x）是数域F上的多项式，且（f（x），g（x））=1，则称多项式f（x）和g（x）是互素的.

定理2.3 多项式f（x）和g（x）互素的充分必要条件是存在多项式u（x）和v（x），使得

u（x）f（x）+v（x）g（x）=1.

证明：由定义2.3与定理2.2可以看出该定理显然成立.

互素是一个重要的概念，它有如下一些性质.若f（x），g（x），h（x）都是多项式，那么，

（1）若h（x）|f（x）g（x）且（h（x），g（x））=1，则h（x）|f（x）；

（2）若（h（x），f（x））=1且（h（x），g（x））=1，则（h（x），f（x）g（x））=1；

（3）若f（x）|h（x），g（x）|h（x）且（f（x），g（x））=1，则f（x）g（x）|h（x）.

证明：性质（1）.由条件（h（x），g（x））=1，一定有两个多项式u（x），v（x）使得

u（x）h（x）+v（x）g（x）=1， （2.13）

式（2.13）两端同乘以多项式f（x）得到

u（x）h（x）f（x）+v（x）g（x）f（x）=f（x）. （2.14）

由条件h（x）|f（x）g（x），显然多项式h（x）整除式（2.14）的左边，因此也一定整除右边，即h（x）|f（x）.

性质（2）.由于（h（x），f（x））=1且（h（x），g（x））=1，因此一定有四个多项式u₁（x），v₁（x），u₂（x），v₂（x）使得

u₁（x）h（x）+v₁（x）f（x）=1，

u₂（x）h（x）+v₂（x）g（x）=1.

把这两个等式相乘，并整理成下面形式

[u₁（x）u₂（x）h（x）+u₁（x）v₂（x）g（x）+u₂（x）v₁（x）f（x）]·h（x）+v₁（x）v₂（x）·f（x）g（x）=1，

由定理2.3知道（h（x），f（x）g（x））=1.

性质（3）.由于f（x）|h（x），因此一定有多项式q（x）使得h（x）=q（x）f（x）.又由于g（x）|h（x），因此g（x）|q（x）f（x），条件（f（x），g（x））=1与性质（1）表明这时必然有g（x）|q（x），因此有多项式q₁（x）使得q₁（x）g（x）=q（x），因此

h（x）=q（x）f（x）=q₁（x）f（x）g（x），

这说明f（x）g（x）|h（x）.证毕.

例2.10 证明：多项式x²+1和x³+1是互素的.

证明：由于有恒等式

所以多项式x²+1和x³+1是互素的，即（x²+1，x³+1）=1.

例2.11 求一个三次多项式f（x），使得f（x）+1能被（x-1）²整除；而f（x）-1能被（x+1）²整除.

解：由题意知，存在一次多项式g（x），h（x），使得

f（x）+1=（x-1）²g（x）， （2.15）(https://www.daowen.com)

f（x）-1=（x+1）²h（x）， （2.16）

式（2.15）、式（2.16）两式相减得

（x-1）²g（x）-（x+1）²h（x）=2. （2.17）

又（x-1）²，（x+1）²互素，且由辗转相除法可以计算出

式（2.17）、式（2.18）两式相比较得

代入式（2.15）或者式（2.16）计算即得

例2.12 求出所有的多项式f（x），使得（x-1）f（x+1）-（x+2）f（x）≡0.

解：从条件可得

（x-1）f（x+1）=（x+2）f（x）. （2.19）

由于（x-1，x+2）=1，所以，x-1|f（x）且x+2|f（x+1），后一整除关系即x+1|f（x）.又（x-1，x+1）=1，所以x²-1|f（x），即f（x）=（x²-1）g（x），其中g（x）是一个多项式.代入式（2.19），得到

（x-1）x（x+2）g（x+1）-（x+2）（x-1）（x+1）g（x）≡0，

由消去律可以得到

xg（x+1）=（x+1）g（x）. （2.20）

式（2.20）表明x|g（x），即有多项式h（x）使得g（x）=xh（x）.代入式（2.20），得

h（x+1）≡h（x）.

于是，

h（x）≡c，

其中c是一个常数.这样就可以得到

f（x）=cx（x²-1）.

定义2.4 若f（x）和g（x）是数域F上的非零多项式，数域F上的多项式h（x）满足条件：

（1）f（x）|h（x）且g（x）|h（x）；

（2）对f（x）和g（x）的任意公倍式h₁（x），都有h（x）|h₁（x），则称h（x）是f（x）和g（x）的最小公倍式.特别地，首项系数为1的最小公倍式通常记作[f（x），g（x）].

例2.13 设f（x）=x²+3x+2，g（x）=x²+4x+3，通过简单计算，可以知道

（f（x），g（x））=x+1，[f（x），g（x）]=x³+6x²+11x+6.

更为一般地，我们可以定义有限多个多项式的最大公因式与最小公倍式.

定义2.5 设f₁（x），f₂（x），…，f_n（x），n≥2，与d（x）都是数域F上的多项式，且满足条件：

（1）d（x）|f_i（x），i=1，2，…，n，即d（x）是f₁（x），f₂（x），…，f_n（x）的公因式；

（2）若F上的多项式d₁（x）满足d₁（x）|f_i（x），i=1，2，…，n，那么一定有d₁（x）|d（x），

则称多项式d（x）为n个多项式f₁（x），f₂（x），…，f_n（x）的最大公因式.

在不计常数因子的情况下，最大公因式是唯一确定的，记首一的最大公因式为

（f₁（x），f₂（x），…，f_n（x））.

此外，我们还可以归纳地定义n个多项式的最大公因式为

（f₁（x），f₂（x），…，f_n（x））=（（f₁（x），f₂（x），…，f_n-1（x）），f_n（x））.

定理2.4 设f₁（x），f₂（x），…，f_n（x），n≥2，与d（x）都是数域F上的多项式，那么d（x）是多项式组f₁（x），f₂（x），…，f_n（x）的最大公因式的充分必要条件是存在数域F上的n个多项式u₁（x），u₂（x），…，u_n（x）使得

u₁（x）f₁（x）+u₂（x）f₂（x）+…+u_n（x）f_n（x）=d（x）.

定义2.6 设f₁（x），f₂（x），…，f_n（x），n≥2，与h（x）都是数域F上的多项式，且满足条件：

（1）f_i（x）|h（x），i=1，2，…，n，即h（x）是f₁（x），f₂（x），…，f_n（x）的公倍式；

（2）若F上的多项式h₁（x）满足f_i（x）|h₁（x），i=1，2，…，n，那么一定有h（x）|h₁（x），则称多项式h（x）为n个多项式f₁（x），f₂（x），…，f_n（x）的最小公倍式.

在不计常数因子的情况下，最小公倍式是唯一确定的，记首一的最小公倍式为

[f₁（x），f₂（x），…，f_n（x）].

此外，我们还可以归纳地定义n个多项式的最大公因式为

[f₁（x），f₂（x），…，f_n（x）]=[[f₁（x），f₂（x），…，f_n-1（x）]，f_n（x）].

习题

2.3.1. 利用辗转相除法，求多项式f（x）和g（x）的最大公因式（f（x），g（x））.

（1）f（x）=x⁴+x³-3x²-4x-1，

g（x）=x³+x²-x-1；

（2）f（x）=x⁴-4x³+1，

g（x）=x³-3x²+1；

（3）f（x）=x⁵+x⁴-x³-3x²-3x-1，

g（x）=x⁴-2x³-x²-2x+1；

（4）f（x）=x⁴-10x²+1，

2.3.2. 求多项式u（x），v（x），使得

u（x）f（x）+v（x）g（x）=（f（x），g（x））.

（1）f（x）=x⁴+2x³-x²-4x-2，

g（x）=x⁴+x³-x²-2x-2；

（2）f（x）=4x⁴-2x³-16x²+5x+9，

g（x）=2x³-x²-5x-4；

（3）f（x）=3x⁵+5x⁴-16x³-6x²-5x-6，

g（x）=3x⁴-4x³-x²-x-2；

（4）f（x）=3x⁷+6x⁶-3x⁵+4x⁴+14x³-6x²-4x+4，

g（x）=3x⁶-3x⁴+7x³-6x+2.

2.3.3. 求多项式u（x），v（x），使得

u（x）f（x）+v（x）g（x）=1.

（1）f（x）=3x³-2x²+x+2，

g（x）=x²-x+1；

（2）f（x）=x⁴-x³-4x²+4x+1，

g（x）=x²-x-1；

（3）f（x）=3x⁴-5x³+4x²-2x+1，

g（x）=3x³-2x²+x-1；

（4）f（x）=x⁵+5x⁴+9x³+7x²+5x+3，

g（x）=x⁴+2x³+2x²+x+1.

2.3.4. 设多项式

f（x）=x³+（1+t）x²+2x+2u

与

g（x）=x³+tx+u

的最大公因式是一个二次多项式，求：t，u.

2.3.5. 如果u（x）f（x）+v（x）g（x）=d（x），且d（x）是f（x）和g（x）的公因式，则d（x）是f（x）和g（x）的最大公因式.

2.3.6. 若f（x），g（x）不全为零，f（x）=f₁（x）d（x），g（x）=g₁（x）d（x），则d（x）是f（x）和g（x）的最大公因式的充分必要条件是（f₁（x），g₁（x））=1.

2.3.7. 如果（f（x），g（x））=1，那么，（f（x）+g（x），f（x）g（x））=1.

2.3.8. 如果（f（x），g（x））=1，那么，（f（x^m），g（x^m））=1.

2.3.9. 求一个5次多项式f（x），使得f（x）-1能被（x-1）3整除，而f（x）能被x³整除.

2.3.10. 设数域F上的多项式f（x）分别被x-1，x-2，x-3除的余式是4，8，16.试求f（x）被（x-1）（x-2）（x-3）除后的余式.

2.3.11. 如果（f（x），g（x））=1，且f（x），g（x）的次数都大于零，则存在唯一的一对多项式u（x），v（x），使得

u（x）f（x）+v（x）g（x）=1

成立，并且有degu（x）<degg（x）及degu（x）<degf（x）.

2.3.12. 求出多项式u（x），v（x），使得

x^mu（x）+（x-1）nv（x）=1，

m，n是正整数.