求最大公约数-欧几里得算法的证明和实现

最大公约数(gcd)算法

求最大公约数有两种算法, 欧几里得算法和更相减损法, 这里只讨论欧几里得算法
算法核心$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$

算法证明

引理: $d|a$并且$d|b$, 那么$x,y,\in Z$情况下, $d|ax+by$
证明:
$$\begin{array}{rl}& \text{由 }d\mid a\text{，可设 }a=d\cdot m(m\in \mathbb{Z})\\ & \text{由 }d\mid b\text{，可设 }b=d\cdot n(n\in \mathbb{Z})\\ & \text{那么：}\\ & ax+by=(d\cdot m)x+(d\cdot n)y=d(mx+ny)\\ & \text{因为 }m,n,x,y\in \mathbb{Z}\text{，所以 }mx+ny\in \mathbb{Z}\\ & \text{因此 }d\mid (ax+by)\end{array}$$
证毕

根据上述引理, 证明欧几里得算法, 假设$u=\gcd (a,b)$, $v=\gcd (b,a\mathrm{mod}b)$, 证明$u=v$只需要证明 $u$能推出$v$并且$v$能推出$u$

首先证明$u$推出$v$
证明:

假设最大公约数是$d$, 因为$d|b$, 因此等式右边$d|b$就是正确的
还需要证明$d|(a\mathrm{mod}b)$
将$a\mathrm{mod}b$展开
$$a\mathrm{mod}b=a-\lfloor \frac{a}{b}\rfloor \cdot b$$
因为引理说明了$d|ax+by$, 将$x$设为$1$, $y$设为$\lfloor \frac{a}{b}\rfloor$
得到$$d|a-\lfloor \frac{a}{b}\rfloor \cdot b$$
也就是说$d|(a\mathrm{mod}b)$
$u$能推出$v$

再证明$v$推出$u$
证明:

设最大公约数是$d$, 由$v$可知, $d|b$, 因此等式左边$d|b$就是正确的
还需要证明$d|a$
由引理可知$d|ax+by$
将$v$展开
$$d|bx+(a\mathrm{mod}b)y$$
继续展开
$$d|bx+(a-\lfloor \frac{a}{b}\rfloor \cdot b)y$$
令$x=\lfloor \frac{a}{b}\rfloor$, $y=1$, 得到
$$d|b\cdot (x-\lfloor \frac{a}{b}\rfloor )+a$$
化简得到
$$d|a$$
$v$能推出$u$

因为$u$能推出$v$并且$v$能推出$u$, 所以$u=v$, 证毕
欧几里得算法时间复杂度$O(\log k)$

代码实现

#include <bits/stdc++.h>

using namespace std;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    while (n--) {
   
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << '\n';
    }

    return 0;
}