辗转相除法的原理解释,辗转相除法的原理证明

辗转相除法是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。这个和更相减损术有着异曲同工之处。

原理：

首先介绍下更相减损术的原理，假设有两个数161和63，我们要求这两个数的最大公因数，不妨假定这个最大公因数为m，我们可以将较大的数161看成63+98，63与98的和161可以被m整除，其中63也可以被m整除，自然98可以被m整除；
所以这个问题就转换为求98和63的最大公因数m（和上面m相等）
将98看成63+35，其中63可以被m整除，和98也能被m整除，故35也可以被m整除；
所以问题进一步转换为求35和63的最大公因数m（和上面m相等）
同理转换为求 (63-35)=>28和35 的最大公因数
然后转换为求28和7的最大公因数
…（一直减呀减）
后来转换为求7和7的最大公因数
最后转换为求7和0的最大公因数
输出第一个数字即可；这就是相减损术的原理
我们发现求28和7的最大公约数，一直减7，一直减7…减到不能减为止。这个不断减7的过程就是除7求余数（即%7）
这样我们可以将相减损术优化成辗转相除法，上面给出了思考过程，有兴趣可以百度严谨的证明过程。

c语言代码如下： #include<stdio.h>int gcd(int a, int b) { int t; while(b!=0) { t=a%b; a=b; b=t; } return a;}int main() { int a,b; scanf("%d%d",&a,&b); printf("gcd=%dn",gcd(a,b)); return 0;}

同理计算最小公倍数：只要用这两个数的乘积除以最大公因数即可
printf(“lcm=%dn”,a*b/gcd(a,b)）