【求最大公约数】求最大公约数的方法及原理?

【求最大公约数】求最大公约数的方法及原理?

【答案】 方法一：短除法
　　把两个数一直除以它们的公约数,取它们的商继续除,直到无约数可除为止.然后把约数全部乘起来,即为最大公约数.
　　例：求12与48的最大公约数.
　　
　　所以12和48的最大公约数是 2×2×3=12
　　
　　方法二：欧几里德算法（辗转相除法）
　　在两个数中,找出大数.用大数除以小数.得到整数商和余数.然后再不断地用除数（原来的小数）除以余数.直到没有余数为止.那么除数即为最大公约数.
　　例：求161与112的最大公约数.
　　161÷112=1……49
　　112÷49=2……14
　　49÷14=3……7
　　14÷7=2
　　所以161和112的最大公约数是 7
　　
　　方法三：《九章算术》更相减损术
　　用大数减小数,得到的差,与减数比大小,然后继续不断地大数减小数.直到减数等于差为止.差即为最大公约数.
　　例：求161与112的最大公约数.
　　161-112=49
　　112-49=63
　　63-49=14
　　49-14=35
　　35-14=21
　　21-14=7
　　14-7=7
　　所以161和112的最大公约数是 7

回答的不错