更相减损之术的道理就是为什么这个算法求两个数的最大公约数的时候是两个数相减然后凑成数对来求解呢?这个方法不是很直观能理解

Question

更相减损之术的道理
就是为什么这个算法求两个数的最大公约数的时候是两个数相减然后凑成数对来求解呢?这个方法不是很直观能理解

Answer 1

第一步：任意给定两个正整数；判断它们是否都是偶数.若是,则用2约简；若不是则执行第二步.
　　第二步：以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的减数和差相等为止.
　　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数.
　　其中所说的“等数”,就是最大公约数.求“等数”的办法是“更相减损”法.

例:用更相减损术求98与63的最大公约数.
　　由于63不是偶数,把98和63以大数减小数,并辗转相减：
　　98-63=35
　　63-35=28
　　35-28=7
　　28-7=21
　　21-7=14
　　14-7=7
　　所以,98和63的最大公约数等于7.