2022/04/欧几里得算法及其证明

定义

$\forall a,b\in \mathbb{N},gcd(a,b)=gcd(b, a\ mod\ b)$ 。

证明

若$a<b$，则$gcd(b,a\ mod\ b)=gcd(b,a)=gcd(a,b)$ 成立。

若$a\geq b$，设$a=k\cdot b+r$，其中$0\leq r<b$，则$r=a\ mod \ b$。

对于$a$，$b$任意的公约数$d$ ,

因为$d\mid a,d\mid k\cdot b$ 故 $a=q_1\cdot d,k\cdot b=q_2\cdot d$ ，所以 $a-k\cdot b=d(q_1-q_2)$ ，故 $d\mid a-k\cdot b$ 即 $d\mid r$。

因此，$d$也是$b$，$r$的公约数。

反之：

对于$b$，$r$的任意公约数$d$。

因为$d\mid b,d\mid r$ 故 $b=q_1\cdot d,r=q_2\cdot d$ ，所以 $k\cdot b+r=d(k\cdot q_1-q_2)$ ，故 $d\mid k\cdot b + r$ 即 $d\mid a$。

因此，$d$也是$a$，$b$的公约数。

综上，$a$，$b$的公约数集合与$b$，$r$的公约数集合相同。于是它们的最大公约数自然也相等。

证毕。

代码实现

复杂度$O(log(a+b))$

递归方式

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

迭代更新

int gcd(int a,int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}