证明过程：

　　

假设用f（x, y）表示x，y的最大公约数，取k = x/y，b = x%y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x, y）= f（y, x%y）（y > 0），如此便可把原问题转化为求两个更小数的最大，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。

 

代码：

用辗转相除法求a b 最大公约数（a b谁大谁小无所谓）：

int GCD( int a , int b ){    int n=a%b;    whie(n != 0) //即： while(n)    {        a = b;        b = n;        n = a % b;    }        return b; //注意这里返回的是b 不是n}

 递归版：

 

int gcd(int a,int b){    if(b==0) return a;    else return gcd(b,a%b);}