用“更相减损术”求最大公因式

维普资讯

4 2

2 0 0 2年第 6期数学通报

用“更相减损术”求最大公因式胡泰培 ( I l I乐山师范学院数学系 6 1 4 0 0 4 )“更相减损术”是我国占代数学中求二整数最大公因数的方法 .古典名著《九章算术》卷一在谈到分数分子分母约去公数有“置分母子之数 . 以少减多 .更相减损求其等也以等数约之 .”这的“等数”就是所说分母分子的最大公因数所谓“更相减损求其等”就是置两个整数，以少减多，反复相减，直到二数相等就得到它们的最大公因数 .例如，求9 l, 4 9的最大公因数 ( 9 1, 4 9 ) .我们有( 9 1, 4 9 )= ( 9 1—4 9, 4 9 )= ( 4 2, 4 9 ) ( 4 2, 7 )=……= ( 7, 7)= 7=

同的最大公园式 .事实上，当‰≠0时，“ )

互

素.因而 l厂 ( ), g ( ) f ( ), ( )有相同的公式，从而也有相同的最大公因式 . 如上引入的多项式一行矩阵，呵执 r矩阵的初等行变换： l 短阵的行可以相交换； Ⅱ 矩阵的某行可乘一非零数； 【 l l 矩阵某行的倍可加于另一行 .

刘徽说：“其所以相减者，皆等数之重叠 .”数9 1, 4 9都是等数 7的重叠 . 对于初学者来说 .“更相减损求等数”比常用的“辗转相除法求最大公因数”要更容易接受些 . 这小奇怪，正如乘法是加法的叠加，除法也是减法的叠加 .乘除法要比加减法高一个层次. 这里要介绍的是，这种“更相减损术”稍作发

展，还可用来求解多项式的最大公因式 .通常求多项式的最大公因式采用带余除法，辗转相除 .这种方法真正使用起来有时并不简单 .用发展了的“更相减损术”有时还简洁明了些为此，先引人多项式的系数矩阵数域 f上的多项式 l厂 ( )= a o +0 I _。+…+Ⅱ I +。 g( )= b o +6 I ’+。。。+b I +b ( 1 )Ⅱ , b∈ F( i:0, 1, 2,…,; : 0, l, 3,…, m)

这些初等行变换作用在多项式的

二行矩阵上，反映了如下事实：1 f ( ), g( )与 g ( ), 厂 ( 1有相同的最大公 式； I 1 . ), c g( )与厂 ( ) . ( )有相同的最大公园式； I l 1 ., ( )+ 培( ), g( )与 H ), g( )有相 I司的最大公因式.这些都是在任何一本《高等代数》教材或习题中，证明了的不争事实 .这里不再证明 .当具体应用这些初等行变换于二行矩阵时，可使它两行出现端有 0 .其时，可平移使两个端 0处于同一列而略去 .这表明多项式“ ) _ )的最大公因式的次数要降低 .反复应用初等行变换，直 N- -行矩阵的两行对应成比例时，就得 ), g ( 2 i: )的最大公 因式 .通过此法的具体使用易见，它把两个数的更相减损发展成了两组数的更相减损 .举例如下： 例 1 求 )= —2 x一4 x !+4 x一 3, g( )= 2 一5 —4 +3的最大公因式 . 解作二行矩阵并进行初等行变换：

的运算，主要表现为其系数问的运算 .因此，常采用分离系数法 .这里也用分离系数法，把多项式 ) . g ( )的系数表示成一个二行矩阵 .当 m= n时，用

(\ 0 一 2 : 5一 4一 d 3 I 1生一 一

4

f\ l 0— 9 0 0 1一f l0 2—5—4 3/ I 2

—5

0—9 0 1—4 3 J

\ 0 : 6 I… b b J』b

( 0 一 5一。 l; 4 ) 3, 一\ (一 5 1 4。 3 ), (… 2】 里旦\①+3 C,『_ 1 4 4 2 0\ 一【 4——

当 m ( ,如 m= n一1 .则用

f 1

—3 0\

f\ 0。 I…0 b n…

‰ I

b 2 b /

l砬

一 l一5 1 4 3厂——一 I一5 1 4 3 J

(\ b b 0 一： 1… 6 一 I o一

㈥…

、、.

(\ 0 :一 1 。 3 )』 一( I~ 13 1一； )』- _ (, ( ) . g( ) )= 一3

在( 3 )这两个矩阵中，把端有 0的行称为短行， 端无 0的

行称为长行 . ( 3 )表示在二行矩阵中，端有 0的短行可以左 l彳彳平行移动 .这种平移反映了这样

个事实：多项式 r ( ) . g ( )与l厂 ( ), x g ( )有相

这个算法比用辗转相除要简洁得多 .一些与最大公因式有关的问题也可用此法处理 . 例 2决定，使， ( )= +( k+6 ) +4 +2, g( )= +( +2 ) +2 k的最大公因式是次式 . f下转第 1页 )一

定理 2设 ( n ):∑/+ , ( m,∈1 1

∑(一1 ) ( 一 c )一 ( )=(一1 ) m+ l=

1

N)。则

+( (一1 ) 一n )/ G两尝纽音散递推，掣数学询 . 9 3

( 2 )

本文来源：https://www.bwwdw.com/article/ang1.html