辗转相除法是求最大公约数和最小公倍数的另一种方法。
具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。把这些数相乘就是最小公倍数。
例如：求112和77的最大公约数。
把112和77并列，用77去除112，商1余35，如下图：
因为余数不是0，所以继续用35去除77，商2余7，如下图：
因为余数不是0，继续用7去除35，商5余0，如下图：
当最后余数是0时，辗转相除的过程已经完成，最后的除数7就是112和77的最大公约数。
辗转相除法的算理是根据：在a=bq+r，中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数；如果反过来说，被除数与除数的最大公约数，就是除数与余数的最大公约数。
如果用辗转相除法求两个数的最大公约数时，最后的余数是1，那么这两个数就是互质数，或者说，它们只有公约数1。
雪帆老师总结一句话：先用一个大数除以一个小数，然后看是否有余数，如果没有，那小数就是他们的最大公因数。否则继续用上一步的除数和余数相除，如果有，继续除，否则最后一步的除数就是最大公因数！
举例
（18,12）=？
18÷12 余6
继续
12÷6 无余数
所以6就是他们的最大公因数
加载中，请稍候......
加载中…