定义
forall a,bin mathbb{N},gcd(a,b)=gcd(b, a mod b) 。
证明
若$a<b$，则gcd(b,a mod b)=gcd(b,a)=gcd(a,b) 成立。
若ageq b，设a=kcdot b r，其中0leq r<b，则r=a mod b。
对于a，b任意的公约数d ,
因为dmid a,dmid kcdot b 故 a=q_1cdot d,kcdot b=q_2cdot d ，所以 a-kcdot b=d(q_1-q_2) ，故 dmid a-kcdot b 即 dmid r。
因此，d也是b，r的公约数。
反之：
对于b，r的任意公约数d。
因为dmid b,dmid r 故 b=q_1cdot d,r=q_2cdot d ，所以 kcdot b r=d(kcdot q_1-q_2) ，故 dmid kcdot b r 即 dmid a。
因此，d也是a，b的公约数。
综上，a，b的公约数集合与b，a的公约数集合相同。于是它们的最大公约数自然也相等。
证毕。
代码实现
复杂度O(log(a b))
递归方式
代码语言：c 复制int gcd(int a,int b){
return b?gcd(b,a%b):a;
}迭代更新
代码语言：c 复制int gcd(int a,int b){
while(b){
int r=a%b;
a=b;
b=r;
}
return a;
}
