辗转相除法求最大公因数的原理
一、辗转相除法可以求两个因数的最大公因数。（欧几里德算法）
1.我们可以用列举法、筛选法及短除法求得，如：6和9的最大公因数（6，9）=3
2.辗转相除法。
9÷6=1……3
6÷3=2
3就是9和6的最大公因数。
再如：30和80的最大公因数。
80÷30=2……20
30÷20=1……10
20÷10=2
10就是30和80的最大公因数。
辗转相除法优点是可以求出两个大数的最大公因数
二、辗转相除法求最大公因数的原理
如果我们要求8251与6105的最大公因数的话，假设8251是这个数x的a倍，再假设6105是x的b倍，那么2146=8251-6105，是x的(a-b)倍，也是x的倍数，而无论这几个数如何加减，甚至相乘，都还是最大公约数的倍数，我们就可以把求8251与6105的最大公约数简化成求2146和6105的最大公约数，再把求2146与6105的最大公约数简化为求3959(=6105-2146)与2146的最大公约数，如此相减往复几次后，会发现两个数变相等了37=37，这个数就是两个原来数的最大公因数。 举个例子9和69-6=3，保留6,36-3=3，保留3,3发现两数相等，为3所以最大公因数为3
9和6的最大公因数，我们知道是3。9是3的倍数，6是3的倍数，那3也一定是3的倍数。
30和80的公因数为m，30是m的倍数，80是m的倍数。80里有的两个30也肯定是m的倍数，剩下的20也会是m倍数。10也会是m的倍数。10=10=m。
