求最大公约数的方法及原理? 数学
网友回答
【答案】 方法一：短除法
把两个数一直除以它们的公约数,取它们的商继续除,直到无约数可除为止.然后把约数全部乘起来,即为最大公约数.
例：求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