普及一点小学数学知识。

辗转相减法

$\bold {Lemma\space1}$

对于 $a>b$，$\gcd(a,b)=\gcd(a-b,b)$。

$\bold{Proof}$

令 $g=\gcd(a,b)$，则 $a=pg,b=qg$。那么 $a-b=(p-q)g$。因此 $\gcd(a-b,b)\ge g$。

同理，令 $h=\gcd(a-b,b)$，则 $a-b=ph,b=qh$。那么 $a=(p+q)h$。因此 $\gcd(a,b)\ge h$。

所以 $\gcd(a,b)=\gcd(a,b)$。

$\mathcal{Q.E.D.}$

辗转相除法

$\bold{Lemma\space 2}$

对于 $a>b$，有 $\gcd(a,b)=\gcd(a\bmod b,b)$。

$\bold{Proof}$

令 $a=kb+r$，则 $\gcd(a\bmod b,b)=\gcd(r,b)$。而 $a$ 到 $r$ 的过程即减去 $k$ 个 $b$。每一次减 $b$ 都保证 $\gcd$ 相等。所以 $\gcd(a,b)=\gcd(a\bmod b,b)$。

$\mathcal{Q.E.D.}$

那么 gcd 就可以这么写：

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

注意到 if 语句中，若 $b=0$，则考虑上一轮的 $a,b$ 一定满足 $a$ 是 $b$ 的倍数。此时应返回上一轮的 $b$，而这正好就是这轮的 $a$。

但是我们怎么保证一定会进入这个 if 终止递归呢？

我们考虑递推定义如下的二元组序列 $(a_i,b_i)$：对于 $i\ge 2$，$(a_i,b_i)=(b_{i-1},a_{i-1}\bmod b_{i-1})$。容易发现每个 gcd(a[i], b[i]) 会调用 gcd(a[i + 1], b[i + 1])。

称两个二元组 $(x,y),(p,q)$ 相等，当且仅当 $x=p$ 且 $y=q$。

我们断言：存在一个有限的 $k$，使得 $b_k=0$。

证明这个结论还需要一个引理。

$\bold{Lemma\space 3}$

对于任意正整数 $a$，满足对于任意 $b\in [1,a]$，$a\bmod b\le \left\lfloor\dfrac{a}{2}\right\rfloor$。

$\bold{Proof}$

若 $b\in \left[1,\left\lfloor\dfrac{a}{2}\right\rfloor+1\right]$，显然成立。否则，$a\bmod b=a-b\le \left\lfloor\dfrac{a}{2}\right\rfloor$。

$\mathcal{Q.E.D.}$

考虑构造一个新的二元组序列 $(u_i,v_i)$，满足：$(u_1,v_1)=(a_1,b_1)$；对于 $i\ge 2$，$(u_i,v_i)=\left(v_{i-1},\left\lfloor\dfrac{u_{i-1}}{2}\right\rfloor\right)$。那么容易得知对于 $i\ge 3$ 有 $v_i=\left\lfloor\dfrac{v_{i-2}}{2}\right\rfloor$。由此可以得知 $v_{2\lfloor\log_2b_1+1\rfloor+1}=0$。令 $k=2\lfloor\log_2b_1+1\rfloor+1$。

通过 $\bold{Lemma\space 3}$，不难把除以 $2$ 下取整和取模联系在一起。

$\bold{Lemma\space 4}$

对于任意正整数 $i$，有 $a_i\le u_i$，$b_i\le v_i$。

$\bold{Proof}$

考虑使用归纳法。当 $i=1$ 时显然成立。

若当 $i\in[1,m]$ 时成立。则对于 $m$ 有 $a_m\le u_m$ 且 $b_m\le v_m$。当 $i=m+1$ 时，$a_{i}=b_m$，$u_i=v_m$，因此 $a_i\le u_i$；$b_i=a_m\bmod b_m\le \left\lfloor\dfrac{a_m}{2}\right\rfloor\le \left\lfloor\dfrac{u_m}{2}\right\rfloor$，$v_i=\left\lfloor\dfrac{u_m}{2}\right\rfloor$，因此 $b_i\le v_i$。所以在 $i\in[1,m+1]$ 时仍然成立。

综上，对于任意正整数 $i$，有 $a_i\le u_i$，$b_i\le v_i$。

$\mathcal{Q.E.D.}$

由此得知 $b_k\le v_k\le 0$。而容易发现 $b_i$ 恒非负。因此 $b_k=0$。

所以我们可以断言：存在一个有限的 $k$，使得 $b_k=0$。

而且我们还分析出来满足上述条件的最小的 $k$ 满足 $k=\mathcal{O}(\log b_1)$。因此，辗转相除法求两个数 $a,b$ 最大公约数的时间复杂度为 $\mathcal{O}(\log n)$，其中认为 $\max\{a,b\}=\mathcal{O}(n)$。