辗转相除法求最大公因数的原理

辗转相除法求最大公因数的原理

一、辗转相除法可以求两个因数的最大公因数。（欧几里德算法）

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。