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

“更相减损术”是我国古代数学中求二整数最大公因数的方法 .古典名著《九章算术》卷一在谈到分数分子分母约去公因数有“置分母子之数 ,以少减多 ,更相减损求其等也 .以等数约之 .”这里的“等数”就是所说分母分子的最大公因数 .所谓“更相减损求其等”就是置两个整数 ,以少减多 ,反复相减 ,直到二数相等就得到它们的最大公因数 .例如 ,求 91 ,49的最大公因数(91 ,49) .我们有(91 ,49) =(91 -49,49) =(4 2 ,49)=(4 2 ,7) =…… =(7,7) =7刘徽说 :“其所以相减者 ,皆等数之重叠 .”数91 ,49都是等数 7的重叠 .对于初学者来说 ,“更相减损求…