求最大公因数的证明~~

我晕，用穷举法都有的。。。
这个的证明很简单，就是gcd(m,n)=gcd(n,m%n)

另外还有一种算法，从效率上来看比欧几里得算法还要更高
int Gcd(int a, int b)
{
if(a == 0) return b;
if(b == 0) return a;
if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a >> 1, b >> 1);
else if(a % 2 == 0) return gcd(a >> 1, b);
else if(b % 2 == 0) return gcd(a, b >> 1);
else return gcd(abs(a - b), Min(a, b));
}

证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.
Hint:
根据除法的定义不难证明:
1 如果d整除u和v, 那么d一定能整除u±v;
2 如果d整除u,那么d也能够整除u的任何整数倍ku.
对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)

纯原理....

我看不懂 老实话 主要我都不知道你哪个是要求的公约数
原理出来了更````