理 (1)若0≠f(x)g(x)∈Kx,则f(x)是f(x)与g(x)的一个最大公因式。 (2)在带余除法f(x)=q(x)g(x)+r(x)中f(x)与g(x)公因式集 和g(x)与r(x)公因式集相同。 设f(x),g(x)∈K(x不全为零,则f(x)与g(x)的最大公因式d(x)存在,且 存在u(x),(x)∈K[x],使得 d(x)=f(r)u(r)+g(r)o(r) 证明:辗转相除法:利用前面引理,当f(x)和g(x)中有一个整除另一个 时,如g(x)|f(x)时,则g(x)为最大公因式 g(x)=f(x)×0+g(x)×1。 由引理(2) 要求f(x)与g(x)的最大公因式,只需求 g(x)与r(x)的最大公因式,且此时r(x)是f(x)与g(x)的组合;再辗转, 用g(x)与r(x)的带余除法得余式,如此往复,得到结论 最大公因式与数域无关
p ê õª úϪ Únµ (1) e 0 6= f(x) | g (x) ∈ K [x]§K f(x) ´ f(x) g (x) úϪ" (2) 3{Ø{ f(x) = q(x)g(x) + r(x) ¥ f(x) g(x) úϪ8 Ú g(x) r(x) úϪ8Ó" ½n f(x), g(x) ∈ K [x] Ø "§K f (x) g (x) úϪ d(x) 3§ 3 u(x), v(x) ∈ K [x]§¦ d(x) = f(x)u(x) + g(x)v(x)" y²µ Î=Ø{µ|^c¡Ún§ f (x) Ú g (x) ¥kØ, §X g (x) | f (x) §K g (x) úϪ§ g (x) = f (x) × 0 + g (x) × 1" dÚn£ 2 ¤§¦ f (x) g (x) úϪ§I¦ g (x) r(x) úϪ§ d r(x) ´ f (x) g (x) |ܶ2Î=§ ^ g (x) r(x) {Ø{{ª§Xd E§(Ø" 5 úϪêÃ'"
定义(互素多项式) 设f(x),g(x)∈K(x,若(f(x),g(x)=1,则称f(x),g(x)互素。 K[x]中两个多项式f(x),g(x)互素的充要条件是存 在l(x),(x)∈Kx],使得 l(x)f(x)+o(x)g(x)=1。 上述定理是有关两个多项式互素的最重要的关系式。 如果(f(x),g(x)=1,且f(x)lg(x)h(x),则f(x)h(x) ⊙如果f1(x)g(x),2(x)g(x),且(f1(x)12(x)=1, 则f1(x)f2(x)g(x); 如果(61(x)g(x)=1,(E2(x),8(x)=1, 则(1(x)2(x)g(x)=1
p ê õª úϪ ½Â (põª) f(x)§g(x) ∈ K [x]§e (f(x), g(x)) = 1§K¡ f (x)§g (x) p" ½n K[x] ¥üõª f(x)§g(x) p¿^´ 3 u(x), v(x) ∈ K [x]§¦ u(x)f(x) + v(x)g(x) = 1" þã½n´k'üõªp'Xª" ½n 1 XJ (f(x), g(x)) = 1§ f(x)|g(x)h(x)§K f(x)|h(x)¶ 2 XJ f1(x)|g(x), f2(x)|g(x)§ (f1(x), f2(x)) = 1§ K f1(x)f2(x)|g(x)¶ 3 XJ (f1(x), g(x)) = 1§(f2(x), g(x)) = 1§ K (f1(x)f2(x), g(x)) = 1"
设f(x)(x)…,f(x)∈Kx不全为零,d(x)∈K(x]满足 od(x)|f(x),Ⅵ1≤i≤n; 如果d1(x)|f(x),Ⅵ1≤i≤n,则d1(x)|d(x), 则称d(x)为f1(x)(x)…fn(x)的最大公因式,首一的最大公因式 记为(f1(x),2(x),……,fn(x)。 易知, f(x)2(x)…,f(x)=(…(1(x)f2(x),3(x),…),fn(x) 并用归纳法可证存在m1(x),u2(x)……,n(x)∈K[x],使得 (61(x),2(x),…,fn(x)=f1(x)a1(x)+2(x)u2(x)+…+fn(x)n(x)
p ê õª úϪ ½Â f1(x), f2(x), . . . , fn(x) ∈ K [x] Ø "§d(x) ∈ K [x] ÷vµ 1 d(x) | fi(x)§∀1 ≤ i ≤ n¶ 2 XJ d1(x) | fi(x)§∀1 ≤ i ≤ n§K d1(x) | d(x)§ K¡ d (x) f1(x), f2(x), . . . , fn(x) úϪ§ÄúϪ P (f1(x), f2(x), . . . , fn(x))" ´§ (f1(x), f2(x), . . . , fn(x)) = ((· · ·((f1(x), f2(x)), f3 (x)), . . .), fn(x)) ¿^8B{y3 u1(x), u2(x), . . . , un(x) ∈ K [x]§¦ (f1(x), f2(x), . . . , fn(x)) = f1 (x) u1 (x)+f2 (x) u2 (x)+ · · ·+fn (x) un (x) "
定理(中国剩余定理) 设f1(x)……,fn(x)∈K(x]两两互素,则对任意给定 的a1(x)…,an(x)∈K(x,必存在8(x),q1(x)……,m(x)∈K[x 使得 g(x)=f(x)9(x)+a1(x),(记为g(x)=a1(x)mod(x),i=1,……,n 证明:f(x)与f1(x)…f-1(x)f+1(x)…·fn(x)互素,所以存 在u1(x),v1(x)使得 f(x)u1(x)+f1(x)…f-1(x)f+1(x)…fn(x)v1(x)=1 于是对任意的1≤k≤n 小(x)v1(x)I6()=∑n(x)01(x)I(x)+0(x)61(x)…-1(x) ∑41(x)2(x)(x)+a(x)-(x)(x)。 取8(x)=∑=141(x)21(x)(x)即可。可知,每个这样的解与给
p ê õª úϪ ½n (¥I{½n) f1 (x), . . . , fn (x) ∈ K [x] üüp§Ké?¿½ a1 (x), . . . , an (x) ∈ K [x]§73 g (x), q1 (x), . . . , qn (x) ∈ K [x]§ ¦ g (x) = fi (x) qi (x)+ai (x), (Pg (x) ≡ ai (x) mod fi (x) §i = 1, . . . , n" y²µfi (x) f1 (x)· · · fi−1 (x)fi+1 (x)· · · fn (x) p§¤± 3 ui (x), vi (x) ¦ fi (x) ui (x) + f1 (x)· · · fi−1 (x)fi+1 (x)· · · fn (x) vi (x) = 1 u´é?¿ 1 ≤ k ≤ n n ∑ i=1 ai (x) vi (x)∏ j6=i fj (x) = n ∑ i6=k ai (x) vi (x)∏ j6=i fj (x) + ak (x)f1 (x)· · · fk−1 (x)fk+1 = n ∑ i6=k ai (x) vi (x)∏ j6=i fj (x) + ak (x) − fk (x) uk (x) " g (x) = ∑ n i=1 ai (x) vi (x) ∏j6=i fj (x) ="§zù) ½ g (x) ∏ n j=1 fj (x) ª"
中国剩余定理 公元前后的《孙子算经》中有“物不知数”问题:“今有物不知其数,三三数之 余二,五五数之余三,七七数之余二,问物几何? 答为“233”。也就是求同余式组 X≡2mod3 x≡3mod5 x≡2mod7 明朝程大位用歌谣给出了该题的解法:“三人同行七十稀,五树梅花廿一枝 七子团圆月正半,除百零五便得知。” (3,5×7)=1,3×(-23)+(35×2)=1 (5,21)=1 (,15)=1,7x(=2)+(15×1 所以 的数是 2×(35×2)+3×(21×1)+2×(15×1)+<3×5×7)×k=233+105
p ê õª úϪ ¥I{½n úc5f²6¥k“ÔØꔯKµ“8kÔØÙê§nnê { §ÊÊê{n §ÔÔê{§¯ÔAÛº” “233”"Ò´¦Ó{ª| x ≡ 2 mod 3 x ≡ 3 mod 5 x ≡ 2 mod 7 ¶ ²§ ^yÑ TK){µ“n<Ó1ÔD§Êärsö{§ Ôfì §Øz"ÊB"” (3, 5 × 7) = 1§3 × (−23) + 35 × 2 = 1¶ (5, 21) = 1§5 × (−4) + 21 × 1 = 1¶ (7, 15) = 1§7 × (−2) + 15 × 1 = 1¶ ¤±§¦ê´ 2× 35 × 2 +3× 21 × 1 +2× 15 × 1 + 3 × 5 × 7 ×k = 233+105k"