用“更相减损术”求最大公因式维普资讯422002年第6期数学通报用“更相减损术”求最大公因式胡泰培(IlI乐山师范学院数学系614004)“更相减损术”是我国占代数学中求二整数最大公因数的方法.古典名著《九章算术》卷一在谈到分数分子分母约去公数有“置分母子之数.以少减多.更相减损求其等也以等数约之.”这的“等数”就是所说分母分子的最大公因数所谓“更相减损求其等”就是置两个整数，以少减多，反复相减，直到二数相等就得到它们的最大公因数.例如，求9l,49的最大公因数(91,49).我们有(91,49)=(91—49,49)=(42,49)(42,7)=……=(7,7)=7=同的最大公园式.事实上，当‰≠0时，“)互素.因而l厂(),g()f(),()有相同的公式，从而也有相同的最大公因式.如上引入的多项式一行矩阵，呵执r矩阵的初等行变换：l短阵的行可以相交换；Ⅱ矩阵的某行可乘一非零数；【ll矩阵某行的倍可加于另一行.刘徽说：“其所以相减者，皆等数之重叠.”数91,49都是等数7的重叠.对于初学者来说.“更相减损求等数”比常用的“辗转相除法求最大公因数”要更简单接受些.这小惊奇，正如乘法是加法的叠加，除法也是减法的叠加.乘除法要比加减法高一个层次.这里要介绍的是，这种“更相减损术”稍作发展，还可用来求解多项式的最大公因式.通常求多项式的最大公因式采纳带余除法，辗转相除.这种方法真正使用起来有时并不简洁.用进展了的“更相减损术”有时还简洁明白些为此，先引人多项式的系数矩阵数域f上的多项式l厂()=ao+0I_。+…+I+Ⅱ。g()=bo+6I’+。。。+bI+b(1),bF(i:0,1,2,…,;:0,l,3,…,m)Ⅱ∈这些初等行变换作用在多项式的二行矩阵上，反映了如下事实：1f(),g()与g(),厂(1有相同的最大公式；I1.),cg()与厂().()有相同的最大公园式；Il1.,()+培(),g()与H),g()有相I司的最大公因式.这些都是在任何一本《高等代数》教材或习题中，证明白的不争事实.这里不再证明.当详细应用这些初等行变换于二行矩阵时，可使它两行消失端有0.其时，可平移使两个端0处于同一列而略去.这表明多项式“)_)的最大公因式的次数要降低.反复应用初等行变换，直N--行矩阵的两行对应成比例时，就得),g(2i:)的最大公因式.通过此法的详细使用易见，它把两个数的更相减损进展成了两组数的更相减损.举例如下：例1求)=—2x一4x!+4x一3,g()=2一5—4+3的最大公因式.解作二行矩阵并进行初等行变换：的运算，主要表现为其系数问的运算.因此，常采纳分别系数法.这里也用分别系数法，把多项式).g()的系数表示成一个二行矩阵.当m=n时，用(\0一2:5一4一d3I1生一一4f\l0—9001一fl02—5—43/I2—50—901—43J\0:6I…bbJ』b(0一5一。l;4)3,一\(一514。3),(…2】里旦\①+3C,『_14420\一【4——当m(,如m=n一1.则用f1—30\f\0。I…0bn…‰Ib2b/l砬一l一5143厂——一I一5143J(\bb0一：1…6一Io一㈥…、、.(\0:一1。3)』一(I~131一；)』-_(,().g())=一3在(3)这两个矩阵中，把端有0的行称为短行，端无0的行称为长行.(3)表示在二行矩阵中，端有0的短行可以左l彳彳平行移动.这种平移反映了这样个事实：多项式r().g()与l厂(),xg()有相这个算法比用辗转相除要简洁得多.一些与最大公因式有关的问题也可用此法处理.例2打算，使，()=+(k+6)+4+2,g()=+(+2)+2k的最大公因式是次式.f下转第1页)一定理2设(n):∑/+,(m,11∈∑(一1)(一c)一()=(一1)m+l=1N)。则+((一1)一n)/G两尝纽音散递推，掣数学询.93(2)