什么是欧几里德定理

欧几里德定理就是辗转相除法的原理，用来求两个整数的最大公约数gcd(a,b)。

推理过程：

辗转相除法是由辗转相减法而来的，如果a和b（假设a>b）的最大公约数是k，那么可以这样表示a和b：

a=x*k,b=y*k；

那么a-b=(x-y)*k，此时(a-b)和b的最大公约数也是k，因为：

如果它俩的最大公约数是k*t的话，那么b可以整除k*t，(a-b)也可以整除k*t，这样的话就可以得出a也可以整除k*t，则a和b的最大公约数是k*t，与假设矛盾。

所以b和(a-b)的最大公约数也是k。

以此方法，反复辗转相减，必定得到最后a=k,b=0，即求出k。

但是减法比较慢，如果a比b大很多的话，需要减好多次，如果用除（取余）的方法就快多了。

本文标签