求两个多项式的最大公因式_串位加减法_

２ 辗 转 相 除法 中的 三 个 变 形
式 的有 效 算 法 是 十分 必 要 的 。 以求 解 多 项 式 最 大 公 式 的 辗转 相 除法 理 论 为 基 础 ，结 合 ＭＡ Ｌ Ｂ的 ＴＡ
特 点 ，设 计 出可 以有 效 求 解 多 项 式 最 大 公 因式 相
关 问题 的一 个 算 法 ，且 此 算 法 编 程 简 单 ，方 便 实 用 ，容 易 推广 。
１ 传 统 求解 多项 式 最 大 公 因式 的 辗 转 相 除 法
传 统 求 解 多 项 式 最 大 公 因式 的辗 转 相 除 法 是 基 于 用 笔 与 纸 计 算 的 ，要 想 用 电脑 来 计 算 ， 要 需
以 ） 示 数 域 Ｆ上 的一 元 多 项 式 环 。 ｆｘ 表 设 （） 与 ｇ 都 是 数 域 Ｆ上 的一 元 多项 式 ， ） 且 ） 的次 数
大 于 或 等 于 ｇ 的 次 数 ， 要 求 出 ） ） 中的 多 项 式
（） ｖｘ ， 与 （）使
改革用笔和纸计算 中的无规律性 。为此 ，对两个 多项式相乘的方法 ，求商式与余式的方法 ，求和 逐 步 代 人 法 等 传 统 方 法 进 行 变 形 ，以获 得 迭 代 算 法 。下 面 以 ） ＋ ｘ ｌ ｇ ＝ ＋ ＝ ３ ＋ ， （） ＋ １为例 来 说 明 算 法 中 的一 些 变 形 。
项 式 的最 大 公 因式 ，因此 ，设 计 多 项 式 最 大） ｇｘ的一 个 最 大 公 因 式 。 与 （） 由 （）中倒 数 第 ２个 式 子 解 出 （） ２ ，再 由 （）中 ２ 倒 数第 ３个 式 子 解 出 ｒ （） ｋ ，利用 逐 步 代 人 法 可 一 求得 （）中 的 ｕ 和 ｖｘ。 １ ） （）

11
数学与计算机科学学院高等代数课件
例 6 令F是有理数域。求出 F x 的多项式
f x 4 x 4 2 x 3 16 x 2 5 x 9, g x 2 x 3 x 2 5 x 4
的最大公因式 d x 以及满足等式
f xux g xvx d x
8
数学与计算机科学学院高等代数课件
由倒数第二个等式移项得 : rk 1 ( x) rk 3 ( x) rk 2 ( x)qk 1 ( x)
代入[1]式整理得 :
rk 3 ( x)v1 ( x) rk 2 ( x)(u1 ( x) v1 ( x)qk 1 ( x)) rk ( x)
16
(1)设a, b, c Z，如果(a, c) 1， , c) 1, 那么(ab, c) 1 (b 。
数学与计算机科学学院高等代数课件
二、多项式互素的概念 1、定义3
如果 F x 的两个多项式除零次多项式外不再有 其它的公因式，我们就说，这两个多项式互素。
2、f ( x)与g ( x)互素 ( f ( x), g ( x)) 1 。
因为h( x) h( x), h( x) f ( x) g ( x),
所以h( x) h( x)[u ( x) g ( x)] [ f ( x) g ( x)]v( x), 即：h( x) g ( x)。
2
数学与计算机科学学院高等代数课件
二、最大公因式的存在性、唯一性 定理 2.3.1(PartI): F [ x] 的任意两个多项式 f x 与 g x 一定有最大公因式。
定理 2.3.1(part II): 如果 d1 x 、d 2 x 是
f x 与 g x 的两个最大公因式，那么：

第一章
多项式
例1.4.1： 设 求
f x x4 3x3 x2 4x 3,
f x , g x ，和 u x , v x , 使 f x , g x u x f x v x g x
第一章 多项式
g x 3x3 10x2 2x 3.
多项式互素的性质。 性质1： f x , h x 1, g x , h x 1, 若 证： 则 f x g x , h x 1.
f x g x v x.
多项式
第一章
证明： 1、若 f x g x 0, 则 f x , g x 的最大公因式是0。 显然有 d x f x u x g x v x , u x , v x 任意。 2、若 f x 0, g x 0, 则 f x , g x 的最大公
d x rk x f x u x g x v x
多项式
第一章
设 d1 x , d2 x 都是 f x , g x 的最大公因式， 则有 d1 x d 2 x , d 2 x d1 x , d 2 x c d1 x 即两个最大公因式之间仅差一个零次因子。 若用 f x , g x 表示 f x , g x 中首项系数为1的 最大公因式，则 f x , g x 唯一确定。
d ( x) f ( x) g( x), d ( x) h( x)
d ( x) g ( x) d ( x) 1. 性质2：若 h x f x g x , 且 h x , f x 1,

就可以)，这是因为 f ( x ) 和 cf ( x ) 具有完全相同的 因式，即
( f ( x ), g( x )) (c1 f ( x ), g( x )) ( f ( x ), c2 g( x )) (c1 f ( x ), c2 g( x )) ,
c1 , c2 为非零常数．
© 2009, Henan Polytechnic University §4 最大公因式
8 8
第一章 多项式
从而有 ( f ( x ),g( x ))=( g( x ),r1 ( x ))
=( r1 ( x ),r2 ( x ))
=…
=( rs1 ( x ),rs ( x ))
=( rs ( x ), 0)
再由上面倒数第二个式子开始往回迭代，逐个消去
rs1 ( x ),
, r1 ( x ) 再并项就得到 rs ( x )=u( x ) f ( x ) v( x ) g( x ).
5 5
有一为0，如 g ( x ) 0，则 f ( x ) 证：若 f ( x )、g( x )
就是一个最大公因式．且 f ( x ) 1 f ( x ) 0 g( x ). 考虑一般情形： f ( x ) 0,
g( x ) 0,
第一章 多项式
用 g ( x ) 除 f ( x ) 得：
若
d1 ( x )、d 2 ( x ) 为 f ( x )、g( x )
的最大公因式，则 d1 ( x )=cd 2 ( x ) ，c为非零常数．
© 2009, Henan Polytechnic University §4 最大公因式
3 3
第一章 多项式
二、最大公因式的存在性与求法

各数系数多项式唯一因式分解定理
次数大于0的复系数多项式 f ( x)的标准分解式为
ls l1 l2 f ( x) a ( x c1） a ( x c2） ...a ( x cs）
次数大于0的实系数多项式 f ( x)的标准分解式为 f ( x) a ( x c1 ) r1 ...( x cs ) rs ( x 2 p1 x q1 ) k1 ...( x 2 pt x qt ) kt
各数域上的不可约多项式 （复系数多项式唯一因式分解定理） 每一个次数大于 0 的复系数多项式在复数域上都可以唯一地分解成一次因式的乘积。 （实数域多项式唯一因式分解定理） 每一个次数大于 0 的实系数多项式在实数域上都可以唯一地分解成一次因式与二次因式乘积。 （△＜0）
中国剩余定理 设m1 , m2 ,..., ms是两两互素的正整数， b1 , b2 ,..., bs是任意给定的 s个整数。 则同余方程组 （ ） x b 1 mod m1 x b （ 2 mod m2） ....................... （ s mod ms） x b 在Z中必有解，如果 c和d是两个解，那么 c d（ mod m1m2 ...ms） 命题1，设f ( x), g ( x) K [ x]，则 deg( f g ) max ｛deg f , deg g｝ deg( fg ) deg f deg g （f与g和差的次数小于等于它 们的较大次数 f与g积的次数 f与g次数的和） 两个非零多项式 (乘积的首项)等于这两个多项式 (首项的乘积） .
例 1 把 f(x)与 g(x)的最大公因式 表示成 f(x)与 g(x)的倍式和 4 3 2 . f(x)=x +3x-2 g(x)=3x -x -7x+4 不可约多项式：只有非 0 数和相伴元的叫不可约多项式。 （唯一因式分解定理）K[x]中任一次数＞0 的多项式都能唯一的分解成数域 K 上有限多个 不可约多项式的乘积。 （算数基本定理）任一大于 1 的整数 a 都能唯一地分解成有限多个素数的乘积。 2 例 1 证明 x +1 在有理数域上不可约 4 2 分解 x +1 在复数域上不可约多项式的乘积。

由 d x p x d x 1 或 d x cp x .
若 d x 1, 则 p x , f x 1.
若 d x cp x , 则 p x f x
第一章 多项式
性质3：若 p x 不可约且 p x f x g x 则 p x f x 或 p x g x. 证： 若 p x f x , 则结论成立； 若 p x
第一章
多项式
2. 性质 性质1 若 p x 不可约，则 cp x 也不可约， c 0, c F .
性质2 若 p x 是不可约多项式， f x F x ,
则 p x f x 或者 p x , f x 1. 证：设 p x , f x d x ,
h x 1 是 f x3 x, g x3 x2 x 1的一个公因式。
定义2(最大公因式) 设 d x 是 f x , g x 的一个公因式。 若 f x , g x 的任一个公因式 h x 均有 h x d x , 则称 d x 是 f x , g x 的最大公因式。 零多项式与任意f(x)的最大公因式是f(x)
则 f x g x , h x 1. 证：
fu hv 1, fgu hgv g
设 d ( x) f ( x) g( x), d ( x) h( x)
d ( x) g ( x) d ( x) 1.
第一章
多项式
性质2：若 h x f x g x , 且 h x , f x 1, 则 h x g x. 证：由(h( x), f ( x)) 1知存在u( x), v( x)使得

4.定理（Theorem） 4.定理（Theorem） 定理 定理2 定理 对 ∀f ( x )、g( x ) ∈ P[ x ]，在P[ x ] 中存在 一个最大公因式 d ( x )，且d ( x ) 可表成 f ( x )、g( x ) 的一个组合， 的一个组合，即 ∃u( x )、v ( x ) ∈ P[ x ] ， 使
定理２ ② 定理２中最大公因式 d ( x )=u( x ) f ( x )+v( x ) g( x ) 中的 u( x )、v ( x ) 不唯一 不唯一.
举例
③ 对于 d ( x), f ( x),g( x) ∈ P[ x], ∃u( x),v( x) ∈ P[ x] ， 使 d(x )=u( x ) f ( x ) + v ( x ) g ( x ) ,但是 d(x ) 未必是
互素的(或互质的 或互质的)． 则称 f ( x ), g ( x ) 为互素的 或互质的 ．
注:
f ( x ),g ( x ) 互素 ⇔ ( f ( x ), g ( x )) = 1 ⇔ f ( x ), g ( x ) 除去零次多项式外
无其它公因式． 无其它公因式．
2．互素的判定与性质
1) 定理3 定理3
高等代数
注:
高等代数
与零多项式0的最 ① ∀f ( x ) ∈ P[ x ] ，f ( x ) 是 f ( x ) 与零多项式 的最 大公因式． 大公因式．
两个零多项式的最大公因式为0． ② 两个零多项式的最大公因式为 ． 的最大公因式， ③ 若 d1 ( x )、d 2 ( x ) 为 f ( x )、g ( x ) 的最大公因式， 为非零常数。 则 d1 ( x )=cd 2 ( x ) ，c为非零常数。 为非零常数 因此，最大公因式不是唯一的，但在可以 因此，最大公因式不是唯一的， 相差一个非零常数倍的意义下是唯一的， 相差一个非零常数倍的意义下是唯一的，两个 不全为零的多项式的最大公因式是非零多项式， 不全为零的多项式的最大公因式是非零多项式， 此时， ( 此时，我们约定用 f ( x ), g( x )) 来表示首项系数 的那个最大公因式。 为1的那个最大公因式。 的那个最大公因式

注 deg f (x)g(x)=0 f (x) = a0≠0且g(x) = b0≠0 命题 f (x), g(x)∈K[x]. f (x)≠0, g(x)≠0,则
f (x)g(x)≠0. 推论 若 f (x) ≠0, f (x) g(x) = f (x) h(x),则 g(x) = h(x).
称为K上关于x 的一元多项式. aixi: 称为第i 次项, ai: 第i 次项系数.
n 次多项式: 当an ≠0时, 次数记为deg f (x)=n. anxn:首项, an:首项系数. a0:常数项.
K上一元多项式全体记为K[x]
K[ x] {an xn an1 xn1 L a0 | n Z0 , ai K,0 i n}
即满足(1) ~ (4)且满足如下性质
(5) c( f ( x) g( x)) cf ( x) cg( x) (6) (c d ) f ( x) cf ( x) df ( x) (7) (cd ) f ( x) c(df ( x)) (8) 1 f ( x) f ( x)
多项式的运算_乘法
定理设f (x), g (x)∈K[x] , 则存在d(x)∈ K[x] , 使得 (f (x), g(x)) = d(x) , 且存在u(x), v(x)∈ K[x], 使 d(x) = u(x) f (x) + v(x) g(x).
证明用Euclidean辗转相除法.
最大公因式_存在性
注1 证明方法即是计算方法. 注2 最大公因式与数域扩大无关. 注3 设f (x), g (x), d(x) ∈ K[x] , 且 d(x) 的首
注2:因为(1) ~ (4), (9) ~ (11), (13), K[x]对加法和乘法 构成有单位元的结合交换环.

r(x)=f(x)-q(x)g(x)
由此可见，如果g(x),r(x)有一个最大 公
因式d(x)，那么d(x)也是f(x),g(x)的一个 最大公 因式。
h
36
定理2 对于P[x]中任意两个多项式 f(x),g(x),在P[x]中存在一个最大公因式d(x)， 且d(x)可以表示成f(x),g(x)的一个线性组合， 即有P[x]中多项式u(x),v(x)使
g ( x ) q 2 ( x ) r 1 ( x ) r 2 ( x )r 2 0
h
25
例题
f 3 x 3 4 x 2 5 x 6 ,g x 2 3 x 1
x2 3x1
|3x34x25x6 | |_3_x_3__9_x2__3_x____ |
3x 13
| 13x28x6 |
|___1_3_x_2__3__9x__1_ |3
f(x)
31x7
(3x13)g(x)(31x7)
h
26
定义５ 数域P上的多项式g(x)称为整除f(x), 如果有数域P上的多项式h(x)使得
f (x) 0 ,那么 g(x)=h(X)
定义4 所有系数在数域P中的多项式的全体，
称为数域P上的一元多项式环，记为P[x],
P称为P[x]的系数域
BACK
h
19
§3 整除的概念
以后讨论都是在某一固定的数域P上的 多项式环中进行。
带余除法 整除 整除的性质
h
20
带余除法
对于P[x]中任意两个多项式f(x)与g(x)，其
35
Байду номын сангаас
h
最大公因式的求法
结论：如果有等式
f(x)=q(x)g(x)+r(x)