高等代数 (65)古今数学思想.pdf

第四章 多项式 4.3 最大公因式 4.3.3 欧几里得辗转相除法 三、欧几里得辗转相除法 引理. f , g 0,r F x f q g r  f , g g ,r .  满足     证明: 记d f , g , e g, r , 与 都是首 多项式 d e e d :     d e 1 . 只需证明 且 d e : f q g r  r f qg   d 是r f qg 的因式  d f , g     f g 是 与 的因式 d g  是 的因式 d e g, r  是 与 的公因式   d g r e d : e g, r e f qg r   g r 是 与 的因式 是 的因式 e f g  是 与 的公因式 e d f , g   Euclid ( ) 算法辗转相除法 g F x f F x , 非零多项式   输入: 多项式   输出: f g d f , g 与 的最大公因式   f , g g ,r f q g r     1 1 1 g , r r , r g q r r     2 1 2 1 1 2