定理6.设f(c),9(α)不全为零,则gcd(f(α), g())存在,并且存在 α(α),b(α)使gcd(f(α), g(α)) = a()f(α) + b()g(α)第一种证法：「要点]降低次数如果f(c),g(α)有一个是0,则结果成立.以下设f(a),g(c)都不等于零对 deg(f)+deg(g)进行归纳当 deg(f)+deg(g)= 0时,gcd(f, g) = 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(α),r(a)使f(α)=g(c)q(c)+r(α) 且 deg(r) < deg(g). 由于deg(r) + deg(g) <deg(f)十deg(g)且g(c),r(）不全为零，根据归纳假设 gcd(r(α),g(a)) 存在,并且有 ai(α),bi(ac)使gcd(r(c),g(c)) = ai(c)r(α) + bi(αc)g(α). 由上面引理得知gcd(f(α),g(c)) = gcd(r(α),g(α)) =ai()(f(α) - g()q(α)) + bi(α)g(α) = ai(α)f(α) +(bi(α) ai()q(α))g(α). 令a() = ai(α),b(c) =bi(α) 一ai(c)q(α) 即可. [注]上面的证明是构造性的,它给出了gcd 的计算方法，叫做辗转相除法(Euclideanalgorithm)
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)
第二种证法：令 T = [a(α)f(α) +b(α)g(α)la(α),b(α) E K[l).由于f(α),g(α)不全为零,在集合I中存在一个非零元素.在I的非零元素中任选一个次数最低的元素 d() =ai()f() +bi(c)g(α).根据带余除法,存在q(α),r(α)使f(α) = d(c)q(c) +r(α),满足 deg(r)< deg(d). 由于r(α) = (1 -ai()q(α))f(c) - (bi(α)q()g(),故 r(α)E .假如 r(α)≠ o,则与 deg(d)的最低性矛盾,故 r(α)= 0.这证明了 d(a)lf(α).同理d(α)lg(α).所以d(α)是f(α)和g(α)的公因式设 h(α)是 f(α),g()的任意一个公因式,则h(α)lai(α)f(c) +bi(c)g(c),即 h(c)|d(α). [注|这种证法是非构造性的
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.求证+1α2m+c2n+1对任何非负整数m,n成立.证明：(c - 1)(α2m + α2n+1)= a2m+1 - a2n+1 + a2n+2 - a2m= a(a2m - a2n) +(α2n+2 - a2m)被2一1整除,故存在h(α)使(a - 1)(α2m + a2n+1) = (α2 - 1)h(r),由此得a2m + a2n+1 = (a + 1)h(c).口
~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.设fi(c),....fn(c)EK[cl不全为零h(c是一个非零多项式。如果对每个i都有h(c)lfi(α),则h(α)称为fi(a),...,fn(α)的一个公因式.设d(α）是fi(α)，...,fn(a)的一个公因式并且具有如下性质：对fi(α),...,fn(α）的任何一个公因式h(α)都有 h(α)ld(α),则d(ac)称为fi(α),..,fn(α)的最大公因式,记作(fi(a),...,fn(a)或gcd(fi(a),...,fn(α)[注]1)如果n=1,则 d(α)=fi(α).2)如果n=2.则新的定义和以前的定义一致。3) 如果 fi(αc)=0, 则gcd(fi(c),..., fn(c))= gcd(fi(α), : .:, fk-1(c), fk+1(c), : .:, fn())
½Â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)).