什么是欧几里德定理

TIPS：本文共有 761 个字，阅读大概需要 2 分钟。

欧几里德定理就是辗转相除法的原理，用来求两个整数的最大公约数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大很多的话，需要减好多次，如果用除（取余）的方法就快多了。

什么是欧几里德定理

欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a，b)=gcd(b，amodb)证明：a可以表示成a=kb+r，则r=amodb假设d是a，b的一个公约数，则有d|a，d|b，而r=a-kb，因此d|r因此d是(b，amodb)的公约数假设d是(b，amodb)的公约数，则d|b，d|r，但是a=kb+r因此d也是(a，b)的公约数因此(a，b)和(b，amodb)的公约数是一样的，其最大公约数也必然相等，得证。欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：

voidswap(int&a，int&b){intc=aa=bb=c}intgcd(inta，intb){if(0==a){returnb}if(0==b){returna}if(a>b){swap(a，b)}intcfor(c=a%bc>0c=a%b){a=bb=c}returnb}

如果觉得《什么是欧几里德定理》对你有帮助，请点赞、收藏，并留下你的观点哦！