3、最大公因式
一、最大公因式的概念
上一篇我们介绍了多项式之间的除法：整除和带余除法。这之后我们就可以探讨一个重要的问题，就是多项式的因式分解问题。在此之前，先来介绍公因式的概念。
定义：$K[x]$上的多项式$f$和$g$的公共因式称为它们的公因式，即若$p$是$f$、$g$的公因式，则有$p|f$、$p|g$。
容易看出公因式有这样几个性质：
1、所有公因式构成一个集合；
2、若$p$是$f$和$g$的公因式，则$cp,c in K$也是，也即公因式的相伴式也是公因式；
3、任意两个多项式之间一定存在公因式$b, deg b = 0$；
4、任意多项式$f$与$0$之间至少存在一个公因式$f$。
公因式中最特殊的是“最大公因式”，定义如下：
若$d$是$f$和$g$的公因式，而$f$、$g$的任一公因式$c$，满足$c|d$，则称$d$是$f$和$g$的最大公因式。
最大公因式有如下的性质：
1、若$f$、$g$不全为$0$且最大公因式存在，则不唯一：若$d_1$、$d_2$都是最大公因式，显然有$d_1 | d_2$、$d_2 | d_1$，即二者相伴；
2、由1立即得：最大公因式在相伴意义下唯一，否则最大公因式将构成一个集合，我们记$(f,g)$是$f$和$g$的首项为1的最大公因式；
3、任意$f$与$0$的公因式$c$一定满足$c|f$，因此$f$是$f$与$0$的一个最大公因式，这样，如果我们规定$0$与$0$的最大公因式是$0$（除此之外$0$不会成为最大公因式），就有：
4、任意多项式都是它和它本身的一个最大公因式。
有了3和4，我们下面讨论的时候自始至终都假设多项式不全为$0$。
除此之外，最大公因式还有如下非常重要的性质：
5、若$f$和$g$的公因式集合等于$p$和$q$的公因式集合，则任意$f$和$g$的最大公因式集合等于$p$和$q$的最大公因式集合。
证明：若$d$是$f$和$g$的最大公因式，则任意$f$和$g$的公因式$c$，$c|d$，由前提，$c$也是$p$和$q$的公因式，那么由定义就知$d$也是$p$和$q$的最大公因式。反过来同样证明。
请大家注意这个性质的对称性要求。此性质的一个直接推论就是：$f$和$g$的最大公因式也是$af$和$bg$的最大公因式，其中$a$、$b in K$。
另一个推论也类似：$ad-bc eq 0$时，$(af+bg,cf+dg) = (f,g)$。
二、最大公因式存在定理
前面讨论的时候，都假设了最大公因式的存在性。但任意两个多项式之间都存在最大公因式吗？这是肯定的，而且最大公因式的性质比我们想的还要更好。在证明这一点之前，我们先来证明一个引理：
引理1：带余除法等式$f = hg + r$中，$f$和$g$的最大公因式的集合等于$g$和$r$的最大公因式的集合。
证明：改造带余除法等式：$r=f-hg$。将两式写在一起：
$f=hg+r$
$r=f-hg$
我们就能发现$f$、$g$的每个公因式也是$g$、$r$的公因式，反过来，$g$、$r$的每个公因式也是$f$、$g$的公因式，这样由性质5，就证明了引理。
有了这个引理，我们来证明最大公因式存在定理：
定理：任意$K[x]$中的多项式$f$、$g$，都存在最大公因式$d$，且最大公因式可以表示成两式的倍式和，即存在$u$、$v$，满足：
$d=uf+vg$
证明：如果两式其中之一是$0$（不妨是$g$），则已经有$f$是最大公因式，且$f=1*f+1*0$，下面设均不是$0$：
做带余除法：
$f=h_1 g+r_1 , deg r_1 < deg g$
继续做：
$g = h_2 r_1 + r_2 , deg r_2 < deg r_1$
不断在带余除法等式里，重新用余式去除以除式，由于度数是不断减小的，总有一个时刻有：
$r_{s-2} = h_{s-1} r_{s-1} + r_s , deg r_s < deg r_{s-1}$
$r_{s-1} = h_s r_s + 0 , s in N^*$
由最后一式，我们知道$r_s$就是$r_s$和$r_{s-1}$的最大公因式。再由引理1和倒数第二式，又知道$r_s$是$r_{s-1}$和$r_{s-2}$的最大公因式，不断向上利用引理1，就明白$r_s$就是$f$和$g$的最大公因式。于是最大公因式的存在性得到了证明。现在来证明定理的后半部分：
倒数第二式表明：$r_s = r_{s-2} - h_{s-1} r_{s-1}$，倒数第三式（未标出）又有：$r_{s-1} = r_{s-3} - h_{s-2} r_{s-2}$，将倒数第三式代入倒数第二式就消去了$r_{s-1}$，不断用更上面的式子逐一消元，就能证明定理的后半部分。
定理的证明过程告诉我们一个求最大公因式的方法，即辗转相除法。不断用余式去除以除式，则一连串式子中最后一个不为$0$的余式就是一个最大公因式。这和求最大公因数的方法相同。
一旦证明了最大公因式的存在性，我们就可以找出几个最大公因式的更多重要性质：
6、若$d$是$f$和$g$的倍式和，且是它们的公因式，那么$d$就是它们的最大公因式。
证明很显然：$f$和$g$的任意一个因式当然也是它们的倍式和的因式，由最大公因式的定义就可以证明该性质。
7、$(f,g)h$是$fh$和$gh$的一个最大公因式，特别地，若$h$首1，则$(f,g)h=(fh,gh)$。
证明：$(f,g)h$当然是$fh$和$gh$的一个公因式。下面不妨设$q$为$fh$和$gh$的任一公因式，就有$fh=sq , gh=tq$。另外，我们有：$(f,g)h = ufh+vgh$，这样就有$(f,g)h = usq+vtq = (us+vt)q$，由$q$的任意性，性质的前半部分就得到了证明。至于后半部分，由最大公因式在相伴意义下唯一，也不难证明。
三、互质多项式
类比整数之间的互质，我们有如下定义：多项式$f$和$g$若$(f,g)=1$，则称二者互质。我们直接给出互质的判定定理：
互质判定：多项式$f$、$g$互质的充分必要条件是存在$u$、$v$使
$uf+vg=1$
证明：必要性已经不用证明，现在证明充分性：
由于$(f,g) | f$、$(f,g) | g$，就有$(f,g) | (uf+vg)$，则推知$(f,g) = 1$。
互质多项式有一些奇妙的性质，基本上用互质判定定理就可以给出证明，现在基本只是列出这些性质：
1、若$f|gh$且$(f,g)=1$，则$f|h$。
这条性质的证法比较重要，因此给出：由于$f$与$g$互质，因此有$uf+vg=1$，则$ufh+vgh=h$，由于$f|gh$，所以就可以得到$f|h$。
2、已知$(f,g)=1$：
若$f|h$且$g|h$，则$fg|h$；若$(f,h)=1$且$(g,h)=1$，则$(fg,h)=1$。
3、不全为$0$时，$(frac{f}{(f,g)} , frac{g}{(f,g)})=1$。（当分母整除分子时，分式也是一个多项式）
4、若$(f,g)=1$，则$(f,f+g)=(g,f+g)=(fg,f+g)=1$。
5、不全为$0$时，有$uf+vg=(f,g)$，此时有$(u,v)=1$。
与互质判定定理类似，我们有不互质判定定理：
不互质判定：$f$与$g$不互质的充分必要条件是存在不为$0$的$u$、$v$，使得
$uf=vg$
而且
$deg u < deg g , deg v < deg f$
证明：
必要性：由$f$与$g$不互质，我们设$d=(f,g) , deg d > 0$，且$f=sd , g=td$。则$tf=sg$，而且一定有$deg t < deg g , deg s < deg f$。
充分性：用反证法。假设满足条件，且$(f,g)=1$，则存在下式：$sf+tg=1$。两边乘以$u$有：
$suf+tug=(sv+tu)g=u$
由于$deg u <deg g$，也就是$deg (sv+tu) < 0$，推出$sv+tu=0$，也即$u=0$，这与前提矛盾，故充分性得证。
四、推广
上面提到的各种定义都可以从两个多项式推广到$n$个多项式，辗转相除法也是可以保留下来的。重复的定义和性质不再说明，下面说明与两个多项式不同的情况：
1、我们有$(f_1,f_2,...,f_n)=((f_1,f_2,...,f_{n-1}),f_n)$。
2、$n$个多项式互质不代表两两互质，即$(f_1,f_2,...,f_n)=1$无法推出$(f_i,f_j)=1 , 1 leq i,j leq n$。
数域$K$上的以上定义、性质也可以向更大的数域$F$推广。这里有几点需要注意：
1、数域的推广可能会增加公因式。譬如$f=x^2+1 , g=x^3+x^2+x+1$在$R$内没有1次公因式，但是在$C$内则有$x+i$与$x-i$两个1次公因式。
2、虽然如此，最大公因式不会随数域的扩大而改变。证明也很简单，只要根据带余除法不随数域扩大而改变即可。这也告诉我们，数域的扩大不改变互质。
数域的缩小一般不是任何时候都能做的，这里就不讨论。
另外，最大公因式，以及下面会介绍的最小公倍式，都可以与整数的最大公因数、最小公倍数类比。
五、最小公倍式
类比于公因式和最大公因式，我们还有公倍式和最小公倍式的概念：
定义：若$f|m$且$g|m$，则称$m$是$f$和$g$的公倍式。
定义：若$m$是$f$和$g$的公倍式，且对任意公倍式$l$，都有$m|l$，则称$m$是$f$和$g$的最小公倍式。
容易看出最小公倍式在相伴意义下也是唯一的，我们记$[f,g]$是首1的最小公倍式。
也很容易看出$0$总是公倍式，但除非$f=g=0$，否则$0$不会是最小公倍式。
同样有最小公倍式存在定理：任意非$0$多项式$f$、$g$存在最小公倍式。
证明：由最大公因式存在定理，设$d=(f,g)$，再设$f=ud , g=vd$，由互质的性质5我们有$(u,v)=1$。对于多项式$uvd$，显然它是$f$、$g$的一个公倍式。
若$l eq 0$是$f$、$g$的公倍式，设$l=sf , l=tg$，则$l = sud = tvd$，进而推出$u|frac{l}{d}$、$v|frac{l}{d}$。由于$(u,v)=1$，由互质的性质2，也就有$uv|frac{l}{d}$，进而$l=puvd$，也就证明了$uvd|l$，这样$uvd$是最小公倍式就得到了证明，也即最小公倍式一定存在。
最小公倍式有这样一个很重要的性质：
假设$f$、$g$首1，有：$[f,g](f,g)=fg$。不再证明。