8 第一章多项式州 元(x)=x-mg)+f.fx)）=x-mgx+i(x), 其中d,与eh分别是多项式f-1(x)与f(x)的首项系数，s>h≥m,并且 degf(x)<degg(x). 于是 f)=( Lehx-m）g(x)+f4(x) h 因此， xh-m bm 上述过程可写成表1,1的形式，这种算法称为Euid长除法 十 ox+xtg+.+xt-wg+wxg=(x)8 设多项式f(x)=anx"+am-1x-l+.+ax+aoeF[x],aeF.记 f八a）=ana"+a-1a-l+.+a1a+ao f(a)称为多项式f(x)在x=a处的值.若f(a)=0,则a称为多项式f(x)的根
⋅ 8 ⋅ 第一章 多 项 式 ¹ fℓ−(x) = ds bm x s−m g(x) + fℓ(x)， fℓ(x) = eh bm x h−m g(x) + fℓ+(x)， 其中 ds 与 eh 分别是多项式 fℓ−(x) 与 fℓ(x) 的首项系数，s > h ⩾ m，并且 deg fℓ+(x) < deg g(x)． 于是 f (x) = ( an bm x n−m + ct bm x t−m + ⋯ + ds bm x s−m + eh bm x h−m )g(x) + fℓ+(x)． 因此， q(x) = an bm x n−m + ct bm x t−m + ⋯ + ds bm x s−m + eh bm x h−m ， r(x) = fℓ+(x)． 上述过程可写成表 1.3.1 的形式，这种算法称为 Euclid 长除法． x mb = )x(g m x − mb + − m x +x b + ⋯ + ⎞ ⎠ b − m an x n−m + b − m ctx t−m + ⋯ + b − m dsx s−m + b − m eh x h−m an x n + an−x n− + ⋯ + an−m x n−m + ⋯ + ax + a −) an x n + b − m anbm−x n− + ⋯ + b − m anb x n−m ctx t + ct−x t− + ⋯ + ct−m t t−m + ⋯ + c −) ctx t + b − m ctbm−x t− + ⋯ + b − m ctb x t−m ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ dsx s + ⋯⋯ + ds−m x s−m + ⋯ + d −) dsx s + ⋯⋯ + b − m dsbx s−m eh x h + ⋯ + eh−m x h−m + ⋯ + e −) eh x h + ⋯ + b − m eh bx h−m pq x q + ⋯ + px + p (q < m) f (x) b − m an x n−m g(x) f(x) b − m ctx t−m g(x) ⋮ ⋮ fℓ−(x) b − m dsx s−m g(x) fℓ(x) b − m eh x h−m g(x) r(x) = fℓ+(x) 表 1.3.1 Euclid 长除法 x − x + x + x − ) x + x − x − x − − x − x − x + x − x − x − x − x + x + x − − x − x − 表 1.3.2 Euclid 长除法（ 例 1.3.1） 设多项式 f (x) = an x n + an−x n− + ⋯ + ax + a ∈ F[x]，a ∈ F．记 f (a) = an a n + an−a n− + ⋯ + aa + a． f (a) 称为多项式 f (x) 在 x = a 处的值．若 f (a) = ，则 a 称为多项式 f (x) 的根．
W51.3整除性与最大公因式 ·9 定理1.3.1的一个重要特例是： 推论1.3.1（剩余定理）设f(x)eF[x],aeF,则存在唯一q(x)eF[x],使得 f(x)=(x-a)q(x)+f(a) (13.2) 证明由定理1.31，存在唯一一对多项式q(x),r(x)∈F[x],使得 fx)=民a)tr(x). 其中degr(x)<1.将x=a代人得到fo)r 例13.1设fx)=x3-x2-43gx10 2+2x-3,求f(x)除 以g(x)的商式q(x)和余式( 解如表1.3.2作Euclid长除法.由此得到 定义13.1设非零多项式g(x)eF[x]如果存在()[x],使得多项式 f(x)=g(x)q(x). 则多项式g(x)称为多项式f(x)的一个因式，而多项式)称为多项式g(x)的 个倍式.这时说多项式g(x)整除多项式f(x记为g)了)否则就说多项式 g(x)不能整除多项式f(x),记作g(x)十f(x). 关于多项式的整除性，有以下性质. 性质13.1如果g(x)fx),h(x)川g(x),则h(x) 性质1.3.2 如果g(x)((5(),则对任意,he[ g(x)川(h(x)(x)+h2()f6() 性质1.3.3如果g(x)川f(x),f(x川g(x),则存在非零的数sF,使得 f(x)=g(x). 上述性质请读者自证之 Pd 推论13.2（因式定理）设f(x)eF[x],aEF则当且仅当f(a)=0时 (x-a)f() 定义132g设多项式xf(x),h(x)EF如果h(x)是(x)与6(x)的 因式，则h(x)称为点G)的一个公因式设C与(x)不全为零如果 首一多项式d(x)是()与()的公因式，而且()与f(x)的每个公因式都是 d(x)的一个因式，则d(x)称为)与(x)的最大公因式，记为 d(x)=(f(x),f(x): 关于两个不全为零的多项式(x)与(x)的最大公因式，有 定理1.3.2任意两个不全为零的多项式(x)与f(x)的最大公因式(x)存 在而且唯一
´ §1.3 整除性与最大公因式 ⋅ 9 ⋅ 定理 1.3.1 的一个重要特例是： 推论 1.3.1（剩余定理）设 f (x) ∈ F[x]，a ∈ F，则存在唯一 q(x) ∈ F[x]，使得 f (x) = (x − a)q(x) + f (a)． (1.3.2) 证明 由定理 1.3.1，存在唯一一对多项式 q(x)，r(x) ∈ F[x]，使得 f (x) = (x − a)q(x) + r(x)， 其中 deg r(x) < ．将 x = a 代入，得到 f (a) = r(x)． ∎ 例 1.3.1 设 f (x) = x + x − x − x − ，g(x) = x + x + x − ，求 f (x) 除 以 g(x) 的商式 q(x) 和余式 r(x)． 解 如表 1.3.2 作 Euclid 长除法．由此得到 q(x) = x − ， r(x) = − x − x − ． ∎ 定义 1.3.1 设非零多项式 g(x) ∈ F[x]．如果存在 q(x) ∈ F[x]，使得多项式 f (x) = g(x)q(x)， 则多项式 g(x) 称为多项式 f (x) 的一个因式，而多项式 f (x) 称为多项式 g(x) 的一 个倍式．这时说多项式 g(x) 整除多项式 f (x)，记为 g(x) ∣ f (x)．否则就说多项式 g(x) 不能整除多项式 f (x)，记作 g(x) ∤ f (x)． 关于多项式的整除性，有以下性质． 性质 1.3.1 如果 g(x) ∣ f (x)，h(x) ∣ g(x)，则 h(x) ∣ f (x)． 性质 1.3.2 如果 g(x) ∣ f(x)，g(x) ∣ f(x)，则对任意 h(x)， h(x) ∈ F[x]， g(x) ∣ (h(x) f(x) + h(x) f(x))． 性质 1.3.3 如果 g(x) ∣ f (x)，f (x) ∣ g(x)，则存在非零的数 λ ∈ F，使得 f (x) = λg(x)． 上述性质请读者自证之． 推论 1.3.2（因式定理）设 f (x) ∈ F[x]，a ∈ F．则当且仅当 f (a) = 时， (x − a) ∣ f (x)． 定义 1.3.2 设多项式 f(x)， f(x)， h(x) ∈ F[x]．如果 h(x) 是 f(x) 与 f(x) 的 因式，则 h(x) 称为 f(x) 与 f(x) 的一个公因式．设 f(x) 与 f(x) 不全为零．如果 首一多项式 d(x) 是 f(x) 与 f(x) 的公因式，而且 f(x) 与 f(x) 的每个公因式都是 d(x) 的一个因式，则 d(x) 称为 f(x) 与 f(x) 的最大公因式，记为 d(x) = ( f(x)， f(x))． 关于两个不全为零的多项式 f(x) 与 f(x) 的最大公因式，有 定理 1.3.2 任意两个不全为零的多项式 f(x) 与 f(x) 的最大公因式 d(x) 存 在而且唯一．
:10. 第一章多项式州 证明唯一性设d(x)与d2(x)都是(x)与f(x)的最大公因式.由最大 公因式的定义，d(x)是(x)与f(x)的一个公因式，而d2(x)是(x)与f(x)的 最大公因式，因此，d(x)川d2(x) 反之，同样有d2(x)川d(x).由性质1.33，存在非零的数入eF,使d(x)=入d2(x) 由于d(x)与d2(x)都是首一多项式，比较上式两边的首项系数，得到入=1，即 d(x)=d2(x) 存在性不妨设x)0,由定理存在多项式9(x)与r1(x),使得 x)=9x)h(x)+n(x) 其中degr(x)<deg() 如果dg()为零多项式，则停止.如果()是非零多项式，则由定理 1.3.1,存在多项式92x当(，使得 f5(x)=q2(x)r(x)+r(x) 其中degr(x)degr. 如果是琴多式则停止。如果2(x)是非零多项式，则重复上述过程 于是得连串的等式： i(x)=q(x)f2(x)+n(x), (1) (x)=q2(x)n(x)+r( (2) (x)=q3(x)r2(x)+3(x). (3) 2(x)=q(x)rk-1()+r(x) () 其中 deg)degn(x)>degrz(x) .>degra(x) 由于deg()是个给定的非负整数，因此，存在某个正整数，使得r,衣)+0，而 41(x)=0,即最后必有 =qe(x)re-1(x) re(x) () re(()re(x). (e+1) (e+1)式表明，r(x)r(x) 人 整除 因此.电(O式，还轴少式.心》等等于是过 ).).) 因此，由(2)，r(x)川f(x).最后，由()式re(x)f(x).所以r(x)是f(x)与f5(x) 的一个公因式. 反之，设h(x)是(x)与f(x)的一个公因式.由()式，h(x)是(x)的因式. 再由(2)式，h(x)是r2(x)的因式，等等.于是h(x)是r-2(x)及re-1(x)的因式.由
⋅ 10 ⋅ 第一章 多 项 式 ¹ 证明 唯一性 设 d(x) 与 d(x) 都是 f(x) 与 f(x) 的最大公因式．由最大 公因式的定义，d(x) 是 f(x) 与 f(x) 的一个公因式，而 d(x) 是 f(x) 与 f(x) 的 最大公因式，因此，d(x) ∣ d(x)． 反之，同样有 d(x)∣d(x)．由性质1.3.3，存在非零的数 λ ∈ F，使 d(x) = λd(x)． 由于 d(x) 与 d(x) 都是首一多项式，比较上式两边的首项系数，得到 λ = ，即 d(x) = d(x)． 存在性 不妨设 f(x) ≠ ．由定理 1.3.1，存在多项式 q(x) 与 r(x)，使得 f(x) = q(x) f(x) + r(x)， 其中 deg r(x) < deg f(x)． 如果 deg r(x) = −∞ 为零多项式，则停止．如果 r(x) 是非零多项式，则由定理 1.3.1，存在多项式 q(x) 与 r(x)，使得 f(x) = q(x)r(x) + r(x)， 其中 deg r(x) < deg r(x)． 如果 r(x) 是零多项式，则停止．如果 r(x) 是非零多项式，则重复上述过程． 于是得一连串的等式： f(x) = q(x) f(x) + r(x)， () f(x) = q(x)r(x) + r(x)， () r(x) = q(x)r(x) + r(x)， () ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ rk−(x) = qk (x)rk−(x) + rk (x)， (k) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 其中 deg f(x) > deg r(x) > deg r(x) > ⋯ > deg rk (x) > ⋯． 由于 deg f(x) 是一个给定的非负整数，因此，存在某个正整数 ℓ，使得 rℓ(x) ≠ ，而 rℓ+(x) = ，即最后必有 rℓ−(x) = qℓ(x)rℓ−(x) + rℓ(x)， (ℓ) rℓ−(x) = qℓ+(x)rℓ(x)． (ℓ + ) (ℓ + ) 式表明，rℓ(x) ∣ rℓ−(x)． 因此，由 (ℓ) 式，rℓ(x) ∣ rℓ−(x)；再由 (ℓ − ) 式，rℓ(x) ∣ rℓ−(x)，等等．于是 rℓ(x) 整除 rℓ−(x)， rℓ−(x)， . . . ， r(x)， r(x)． 因此，由 ()，rℓ(x) ∣ f(x)．最后，由 () 式 rℓ(x) ∣ f(x)．所以 rℓ(x) 是 f(x) 与 f(x) 的一个公因式． 反之，设 h(x) 是 f(x) 与 f(x) 的一个公因式．由 () 式，h(x) 是 r(x) 的因式． 再由 () 式，h(x) 是 r(x) 的因式，等等．于是 h(x) 是 rℓ−(x) 及 rℓ−(x) 的因式．由
“51.3整除性与最大公因式 ·11 (0式，h(x)是r(x)的一个因式. 因此，如果r(x)的首项系数为a,则由最大公因式的定义，d(x)=ar(x)是 f(x)与(x)的最大公因式 定理1.3.2关于多项式(x)与f(x)的最大公因式的存在性证明给出了求最 大公因式的一个方法，即所谓辗转相除法. 其过程如下：设f(x),f(x)∈Fx]deg(Gx)degf(x).先对f(x)与f(x) 用Euclid长除法，得到商式q(x)与余式)，degx)deg(x):在进行长除法 时，将商式q(x)记人表133的右边 f(x) f(x) f(x】 91(x) -）9(x)f(x)4 )92(n)】9(x(x) n(x) r2(x)(x) 表1.3.3 W表13.4 如果r(x)是零多项式，则停止.如果(x)是非零多项式，则对()和(x) 用长除法，得到商式q(x)与余式rn(x),dcg,(dega()在进行长除法时，将 商式92(x)记入表1.3.4的左边. q2(x) f2(x) f(x) ）q2(x)n(x)-）(x)(x) 94(x) r2(x) (x) g3(x -）9(x)r(x)-）9(x)3( 96(x) r4(x) r( 表13.5 如果(x是多项式，则停止.如果)是非零多项式，则对()和r2(x) 用长除法，得到箭式(x)和余式r,(x),并把商式q人记人表3.5的右边. 如此继续，即可求得(x)与f(x)的最大公因式， 例1.3.2求多项式(x)+3x3-x24x3与(x)-3x310x2+2x-3的 最大公因武 解如表36所示对多项式6(x)和5)作银转相除法 因此，2(x)=9x+2P,0)片0，于是，())=x+3. 定理13.3设不全为零的多项式f(x)g(x)eF[x],d(x)是f(x)与g(x)的最 大公因式.则存在多项式u(x),v(x)∈F[x],使得 f(x)u(x)+g(x)v(x)=d(x). (13.3) 证明记f(x)=(x),g(x)=f(x).由定理13.2的证明，存在多项式q(x) 92(x),9k1(x)和r(x),r2(x),r(x),使得
´ §1.3 整除性与最大公因式 ⋅ 11 ⋅ (ℓ) 式，h(x) 是 rℓ(x) 的一个因式． 因此，如果 rℓ(x) 的首项系数为 a，则由最大公因式的定义，d(x) = a − rℓ(x) 是 f(x) 与 f(x) 的最大公因式． ∎ 定理 1.3.2 关于多项式 f(x) 与 f(x) 的最大公因式的存在性证明给出了求最 大公因式的一个方法，即所谓辗转相除法． 其过程如下：设 f(x)， f(x) ∈ F[x]，deg f(x) ⩾ deg f(x)．先对 f(x) 与 f(x) 用 Euclid 长除法，得到商式 q(x) 与余式 r(x)，deg r(x) < deg f(x)；在进行长除法 时，将商式 q(x) 记入表 1.3.3 的右边． f(x) f(x) q(x) −) q(x) f(x) r(x) 表 1.3.3 q(x) f(x) f(x) q(x) −) q(x)r(x) −) q(x) f(x) r(x) r(x) 表 1.3.4 如果 r(x) 是零多项式，则停止．如果 r(x) 是非零多项式，则对 f(x) 和 r(x) 用长除法，得到商式 q(x) 与余式 r(x)，deg r(x) < deg r(x)，在进行长除法时，将 商式 q(x) 记入表 1.3.4 的左边． q(x) f(x) f(x) q(x) −) q(x)r(x) −) q(x) f(x) q(x) r(x) r(x) q(x) −) q(x)r(x) −) q(x)r(x) q(x) r(x) r(x) q(x) ⋮ ⋮ ⋮ ⋮ 表 1.3.5 如果 r(x) 是零多项式，则停止．如果 r(x) 是非零多项式，则对 r(x) 和 r(x) 用长除法，得到商式 q(x) 和余式 r(x)，并把商式 q(x) 记入表 1.3.5 的右边． 如此继续，即可求得 f(x) 与 f(x) 的最大公因式． 例 1.3.2 求多项式 f(x) = x +x − x −x − 与 f(x) = x +x + x − 的 最大公因式． 解 如表 1.3.6 所示，对多项式 f(x) 和 f(x) 作辗转相除法． 因此，r(x) = x + ，r(x) = ．于是，( f(x)， f(x)) = x + ． ∎ 定理 1.3.3 设不全为零的多项式 f (x)， g(x) ∈ F[x]，d(x) 是 f (x) 与 g(x) 的最 大公因式．则存在多项式 u(x)， v(x) ∈ F[x]，使得 f (x)u(x) + g(x)v(x) = d(x)． (1.3.3) 证明 记 f (x) = f(x)，g(x) = f(x)．由定理 1.3.2 的证明，存在多项式 q(x)， q(x)， . . . ， qk+(x) 和 r(x)，r(x)， . . . ，rk (x)，使得
12 第一章多项式州 3x3+10x2+2x-3=f5(x) x4+3x3-x2-4x-3=f(x) -）x4+9x3+x2-x 3x3+10x2+2x-3=f(x -x3-3x2-3x-3 19 -)3x23+15x2+18x -）-x23-9x2-x+ 9 -5x2-16x-3 3x-号x-号=n() -）-5x2-25xt30 9x+27=() 24-碧=n(x) )-2 -9x-95 0 -）-号x-9 0=r3(x) 表13.6辗转相除法（例1.3.2） fi(x)=qi(x)f(x)+n(x). (①) fx)=4x)(x)+r2(x, (2) rx)=q3(x)r2(x)+r(x) -3(x=qk-(x)rk-2(x)+-(x) k-1) r2()=qk(x)r-()+r(x), (k) x)=)(x). (k+1) 其中 degf(x)>degn(x)>degra(x)>.>degre()0; 而且，为G的首项系数。由式得到 Ad(x)=r-2(x)-r-(x)q(x). 设出(x)=1(x)4(x),上式为 d(x)=(x)+r-()vi(x) 把式(k-1)代入E式，得到 d(x)=r-3(y(x)k-2(x(x)qk(y()】 记(x)=n(x),(x)=a(xq-(x)m(,上武即为 Ad(x)=r-3(x)u2(x)+r-2(x)v2(x) 逐个地把以上等式代入.假设进行了k-2次，得到 Ad(x)=f(x)uR-(x)+r(x)v-i(x). 最后把式()代人上式，得到
⋅ 12 ⋅ 第一章 多 项 式 ¹ x + x + x − = f(x) x + x − x − x − = f(x) x −) x + x + x − x − x x + x + x − = f(x) − x − x − x − − −) x + x + x −) − x − x − x + −x − x − − x − x − = r(x) −) −x − x − x + = r(x) − x − x − = r(x) − x −) − x − x x + = r(x) − x − − −) − x − = r(x) 表 1.3.6 辗转相除法（例 1.3.2） f(x) = q(x) f(x) + r(x)， () f(x) = q(x)r(x) + r(x)， () r(x) = q(x)r(x) + r(x)， ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ rk−(x) = qk−(x)rk−(x) + rk−(x)， (k − ) rk−(x) = qk (x)rk−(x) + rk (x)， (k) rk−(x) = qk+(x)rk (x)， (k + ) 其中 deg f(x) > deg r(x) > deg r(x) > ⋯ > deg rk (x) ⩾ ； 而且 rk (x) = λd(x)，λ 为 rk (x) 的首项系数．由式 (k) 得到， λd(x) = rk−(x) − rk−(x)qk (x)． 设 u(x) = ，v(x) = −qk (x)，上式为 λd(x) = rk−u(x) + rk−(x)v(x)． 把式 (k − ) 代入上式，得到 λd(x) = rk−(x)v(x) + rk−(x)(u(x) − qk−(x)v(x))． 记 u(x) = v(x)，v(x) = u(x) − qk−(x)v(x)，上式即为 λd(x) = rk−(x)u(x) + rk−(x)v(x)． 逐个地把以上等式代入．假设进行了 k − 次，得到 λd(x) = f(x)uk−(x) + r(x)vk−(x)． 最后把式 () 代人上式，得到