定义

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

证明

a<ba<b,则gcd(b,a mod b)=gcd(b,a)=gcd(a,b)gcd(b,a\ mod\ b)=gcd(b,a)=gcd(a,b) 成立。

aba\geq b,设a=kb+ra=k\cdot b+r,其中0r<b0\leq r<b,则r=a mod br=a\ mod \ b

对于aabb任意的公约数dd ,

因为da,dkbd\mid a,d\mid k\cdot ba=q1d,kb=q2da=q_1\cdot d,k\cdot b=q_2\cdot d ,所以 akb=d(q1q2)a-k\cdot b=d(q_1-q_2) ,故 dakbd\mid a-k\cdot bdrd\mid r

因此,dd也是bbrr的公约数。

反之:

对于bbrr的任意公约数dd

因为db,drd\mid b,d\mid rb=q1d,r=q2db=q_1\cdot d,r=q_2\cdot d ,所以 kb+r=d(kq1q2)k\cdot b+r=d(k\cdot q_1-q_2) ,故 dkb+rd\mid k\cdot b + rdad\mid a

因此,dd也是aabb的公约数。

综上,aabb的公约数集合与bbrr的公约数集合相同。于是它们的最大公约数自然也相等。

证毕

代码实现

复杂度O(log(a+b))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;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)