定理6.设f(x),9(x)不全为零,则 gcd(f(r), g(a) 存在,并且存在a(x),b(x)使 gcd(f(a), g(a))=a(a)f(r)+b(a)g(a) 第一种证法:{要点降低次数 如果f(x),g(x)有一个是0,则结果成立以下 设∫(x),g(x)都不等于零 对deg(f)+deg(g)进行归纳 当deg(f)+deg(g)=0时, gcd(, 9)=1 结论成立
½n6. f(x), g(x) Ø ",K gcd(f(x), g(x)) 3,¿ 3 a(x), b(x) ¦ gcd(f(x), g(x)) = a(x)f(x) + b(x)g(x). 1«y{: [:] ü$gê XJ f(x), g(x) k´ 0, K(J¤á.±e f(x), g(x) ÑØ u". é deg(f) + deg(g) ?18B. deg(f) + deg(g) = 0 , gcd(f, g) = 1. (ؤá.
当deg(f)+deg(g)>0时,设deg(f)≥deg(g 根据带余除法,存在q(x),r(x)使∫(x)=g(x)q(x)+ x)且deg(r)<deg(g).由于deg(r)+ deg(f)+deg(g)且g(x),r(x)不全为零,根据归 纳假设god(r(x),g(x)存在,并且有a1(x),b1(x) 使gcd(r(x),g(x)=a1(x)r(x)+b1(x)g(x)由上 面引理得知gd(f(x),9(x)=gcd(r(x),g(x) a1(x)(f(x)-9(x)q(x)+b1(x)g(x)=a1(x)f(x)+ (b1(a)=a1(aq(a))g(c). a(a)=a1(a), b(c) b1(x)-a1(x)q(x)即可.口 注]上面的证明是构造性的它给出了gd的计 算方法,叫做辗转相除法( Euclidean algorithm)
deg(f) + deg(g) > 0 , deg(f) ≥ deg(g). â{Ø{,3q(x), r(x) ¦ f(x) = g(x)q(x)+ r(x) deg(r) < deg(g). dudeg(r) + deg(g) < deg(f) + deg(g) g(x), r(x) Ø ", â8 Bb gcd(r(x), g(x)) 3,¿ k a1(x), b1(x) ¦gcd(r(x), g(x)) = a1(x)r(x) + b1(x)g(x). dþ ¡Úngcd(f(x), g(x)) = gcd(r(x), g(x)) = a1(x)(f(x) − g(x)q(x)) + b1(x)g(x) = a1(x)f(x) + (b1(x) − a1(x)q(x))g(x). -a(x) = a1(x),b(x) = b1(x) − a1(x)q(x) =. ✷ [5] þ¡y²´E5,§Ñ gcd O {,Î=Ø{(Euclidean algorithm)
第二种证法: 令={a(x)f(x)+bx)9(x)a(x),b(x)∈K[c} 由于f(x),g(x)不全为零在集合r中存在一个非 零元素.在的非零元素中任选一个次数最低的 元素d(x)=a1(x)f(x)+b1(x)g(x 根据带余除法,存在q(x),r(x)使 f(a)=d(a)q( )+r(r), 满足deg(r)<deg(d).由于 r(x)=(1-a1(x)q(x)f(x)-(b1(x)q(x)(x), 故r(x)∈r.假如r(x)≠0,则与deg(d)的最 低性矛盾,故r(x)=0.这证明了d(x)f(x).同 理d(x)9(x).所以d(x)是f(x)和g(x)的公因式 设h(x)是f(x),g(x)的任意一个公因式,则 h(x)a1(x)f(x)+b1(x)9(x) 即h(x)d(x)口 注]这种证法是非构造性的
1«y{: - Γ = {a(x)f(x) + b(x)g(x)|a(x), b(x) ∈ K[x]}. duf(x), g(x) Ø ",38Ü Γ ¥3 ". 3 Γ "¥?Àgê$ d(x) = a1(x)f(x) + b1(x)g(x). â{Ø{,3 q(x), r(x) ¦ f(x) = d(x)q(x) + r(x), ÷v deg(r) < deg(d). du r(x) = (1 − a1(x)q(x))f(x) − (b1(x)q(x))g(x), r(x) ∈ Γ. bX r(x) 6= 0, K deg(d) $5gñ, r(x) = 0. ùy² d(x)|f(x). Ó n d(x)|g(x). ¤± d(x) ´ f(x)Ú g(x) úϪ. h(x) ´ f(x), g(x) ?¿úϪ,K h(x)|a1(x)f(x) + b1(x)g(x), = h(x)|d(x). ✷ [5]ù«y{´E5.
例5.求证x+1x2m+x2n+对任何非负整数m,n 成立 证明 m 2m+1 2n+1 2n+2 2 2m )+(x 2m 被x2-1整除故存在h(x)使 (x-1(x20+x2+1)=(x2-1)h(x 由此得 x2m+x2n+=(x+1)h(x)
~5. ¦y x+ 1|x 2m +x 2n+1 é?ÛKê m, n ¤á. y²: (x − 1)(x 2m + x 2n+1) = x 2m+1 − x 2n+1 + x 2n+2 − x 2m = x(x 2m − x 2n ) + (x 2n+2 − x 2m) x 2 − 1 Ø,3 h(x) ¦ (x − 1)(x 2m + x 2n+1) = (x 2 − 1)h(x), dd x 2m + x 2n+1 = (x + 1)h(x). ✷
定义4.设f1(x),…,,fn(x)∈K[x不全为零,h(x 是一个非零多项式。如果对每个都有h(x)f(x) 则h(x)称为f1(x),,f(x)的一个公因式设d(x) 是f1(x),…,fn(x)的一个公因式并且具有如下性 质:对f(x),,fn(x)的任何一个公因式h(x)都 有h(x)d(x),则d(x)称为f1(x),,fn(x)的最大 公因式,记作(f1(x),,f1(x)或gd(f(x),…,fn(x) 注 1)如果m=1,则dx)=f1(x 2)如果m=2,则新的定义和以前的定义 致 3)如果f(x)=0,则 gcd(fi( ),.. ,fn(r)) =gcd(f1(x),,…,fk-1(x),fk+1(x),,,fn(x)
½Â4. f1(x), . . . , fn(x) ∈ K[x] Ø ",h(x) ´"õª"XJéz i Ñk h(x)|fi(x), K h(x) ¡f1(x), . . . , fn(x) úϪ. d(x) ´f1(x), . . . , fn(x) úϪ¿ äkXe5 : éf1(x), . . . , fn(x) ?ÛúϪ h(x) Ñ k h(x)|d(x), Kd(x) ¡ f1(x), . . . , fn(x) úϪ, P (f1(x), . . . , fn(x)) ½ gcd(f1(x), . . . , fn(x)). [5] 1) XJ n = 1, K d(x) = f1(x). 2) XJ n = 2, K#½ÂÚ±c½Â " 3) XJ fk(x) = 0, K gcd(f1(x), . . . , fn(x)) = gcd(f1(x), . . . , fk−1(x), fk+1(x), . . . , fn(x)).