欧几里得定理是什么定理,欧几里德定理

清脆的柠檬定理:

gcda, b) = gcdb, a%b)

证明：
我们首先约定：m = gcda,b) , n = gcdb, q) , a = b*p +q。（这里的gcd含义跟上面一样，q的含义跟后面式子同） 
1.  m 是a,b的最大公约数，那么m整除a,b
     q = a – b*p
     m也可以整除q
    =>m就是b和q的公约数
    =>n是b,q的最大公约数
    =>n >=m

2. =>n 是q,b的最大公约数，那么n整除q,b
    =>a = b*p + q
    =>n也可以整除a
    =>n就是b和a的公约数
    =>m是b,a的最大公约数
    =>m >= n

3.q=a%b
综上所述，那么我们可以得出 n = m,及gcda, b) = gcdb ,a%b) 

实现：

int gcda, b){ifb == 0)return a;return gcdb, a%b);}

三目运算符优化： 

int gcda, b){return b == 0?a:gcdb, a%b);} 拓展清脆的柠檬定理：