求 greatest common divisor 不需要列出所有 divisors。关键是把一对整数换成更小、但 common divisors 完全相同的一对，再重复这个过程。

Greatest common divisors

设 $a,b\in\mathbb Z$，并且两者不同时为零。它们的 greatest common divisor 记作 $\gcd(a,b)$，是同时整除 $a$ 与 $b$ 的最大正整数。等价地，$d=\gcd(a,b)$ 表示

$$\boxed{ d>0,\qquad d\mid a,\qquad d\mid b, \qquad c\mid a\text{ and }c\mid b\Longrightarrow |c|\le d. }$$

最后一个条件中的 absolute value 也涵盖了负的 common divisors。特别地，当 $a\ne0$ 时，

$$\gcd(a,0)=|a|.$$

这里排除 $(0,0)$，因为每个非零整数都能整除这两个数，所以不存在最大的正 common divisor。

例如，$16$ 与 $24$ 的正 common divisors 是 $1,2,4,8$，因此

$$\gcd(16,24)=8.$$

为什么列出 divisors 的方法很慢

对正整数 $n$，直接做法会测试直到 $\sqrt n$ 为止的候选 divisors。找到不超过这个位置的 divisor 后，还能得到与它配对的 divisor $n/d$，所以大于 $\sqrt n$ 的 divisors 也不会漏掉。若 $n$ 的二进制输入长度是 $L$，那么 $L\approx\log_2 n$，而 trial divisions 的数量大约是

$$\sqrt n=2^{\frac12\log_2 n}\approx(\sqrt2)^L.$$

这相对于输入位数是 exponential complexity。Euclid's algorithm 不需要进行这种 divisor search。

Division algorithm

对任意 $a,b\in\mathbb Z$，若 $b\ne0$，则存在唯一整数 $q$ 和 $r$，使得

$$\boxed{a=qb+r, \qquad 0\le r<|b|.}$$

整数 $q$ 称为 quotient，$r$ 称为 remainder。Remainder condition 是 theorem 的一部分；若去掉它，会有许多不同的商和余数组合（quotient–remainder pairs）满足 $a=qb+r$。

Existence

先设 $b>0$。若 $a\ge b$，long division，或重复减去 $b$，会得到符合范围要求的 quotient 与 remainder。若 $a<b$，选择足够大的非负整数 $k$，使 $a+kb\ge b$。对 $a+kb$ 使用前一种情况：

$$a+kb=q'b+r, \qquad 0\le r<b.$$

两边减去 $kb$，得到 $a=(q'-k)b+r$。若 $b<0$，先对正数 $-b$ 使用前面的结论，再把 $q'(-b)$ 改写为 $(-q')b$。这样就覆盖了所有非零整数 $b$。

Negative-dividend 例子

Quotient 可以是负数。取 $a=-5$、$b=3$，则

$$-5=3(-2)+1, \qquad 0\le1<3.$$

因此 quotient 是 $-2$，remainder 是 $1$。

Uniqueness proof

假设有两组 quotient–remainder pairs 都满足 theorem：

$$\begin{aligned} a&=q_1b+r_1, & 0&\le r_1<|b|,\\ a&=q_2b+r_2, & 0&\le r_2<|b|. \end{aligned}$$

把两个等式相减：

$$0=(q_1-q_2)b+(r_1-r_2), \qquad r_2-r_1=(q_1-q_2)b.$$

所以 $b\mid(r_2-r_1)$。Remainder bounds 同时给出

$$-|b|<r_2-r_1<|b|.$$

$b$ 的倍数中，严格位于 $-|b|$ 与 $|b|$ 之间的只有 $0$。因此 $r_2-r_1=0$，从而 $r_1=r_2$。回到相减后的等式，再使用 $b\ne0$，得到

$$(q_1-q_2)b=0 \quad\Longrightarrow\quad q_1=q_2.$$

所以 quotient 与 remainder 都是唯一的。

Gcd reduction theorem

设 $a,b,q,r\in\mathbb Z$，并且 $(a,b)\ne(0,0)$。若

$$a=qb+r,$$

则

$$\boxed{\gcd(a,b)=\gcd(b,r).}$$

这个 theorem 不仅保持 gcd 的数值不变；两对数的 common divisors 完全相同。

通过 common-divisor sets 证明

定义

$$C(u,v)=\{c\in\mathbb Z\mid c\mid u\text{ and }c\mid v\}.$$

分别证明两个包含关系（set inclusions）。

任取 $c\in C(a,b)$。于是 $c\mid a$ 且 $c\mid b$。既然一个数整除 $b$，它也整除 $qb$，difference property 给出

$$c\mid(a-qb)=r.$$

所以 $c$ 同时整除 $b$ 与 $r$，即 $c\in C(b,r)$。因此 $C(a,b)\subseteq C(b,r)$。

反过来，任取 $c\in C(b,r)$。于是 $c\mid b$ 且 $c\mid r$，所以 $c$ 整除它们的 integer linear combination

$$qb+r=a.$$

因此 $c$ 同时整除 $a$ 与 $b$，即 $c\in C(a,b)$。所以 $C(b,r)\subseteq C(a,b)$。

两个包含关系说明

$$C(a,b)=C(b,r),$$

因此两个集合的最大正元素相同，也就是 $\gcd(a,b)=\gcd(b,r)$。

Euclid's algorithm

对正整数输入，令 $r_{-2}=a$、$r_{-1}=b$，再重复使用 division algorithm：

$$\begin{aligned} a&=q_0b+r_0, & 0&\le r_0<b,\\ b&=q_1r_0+r_1, & 0&\le r_1<r_0,\\ r_0&=q_2r_1+r_2, & 0&\le r_2<r_1,\\ &\hspace{2.5em}\vdots \end{aligned}$$

每一步都保持 gcd 不变。令 $m$ 是第一个满足 $r_m=0$ 的下标，此时停止，并返回正 divisor $r_{m-1}$。若第一次 division 的 remainder 已经是零，就返回 $r_{-1}=b$。

为什么 algorithm 一定终止

每个非零 remainder 都是 nonnegative integer，并且严格小于前一个正 divisor。若第一个 remainder 不是零，这些正 remainders 会形成 strictly decreasing sequence。这样的 sequence 不可能无限延续，所以最终一定出现零 remainder。

若 $r_m=0$ 是第一个零 remainder，则最后一次 division 的正 divisor 是 $r_{m-1}$。重复使用 reduction theorem 得到

$$\gcd(a,b)=\gcd(r_{-2},r_{-1})=\cdots=\gcd(r_{m-2},r_{m-1})=r_{m-1}.$$

例：$\gcd(35,21)$

$$\begin{aligned} 35&=1(21)+14,\\ 21&=1(14)+7,\\ 14&=2(7)+0. \end{aligned}$$

最后一个非零 remainder 是 $7$，所以

$$\gcd(35,21)=7.$$

Bézout's identity

设 $a,b\in\mathbb Z$ 不同时为零，并令 $d=\gcd(a,b)$。Bézout's identity 说明存在整数 $s$、$t$，使得

$$\boxed{d=sa+tb.}$$

$s$ 与 $t$ 称为 Bézout coefficients。它们不一定为正，也不一定唯一。

为什么 back-substitution 有效

每个 Euclidean step 都可以改写为

$$r_i=r_{i-2}-q_i r_{i-1}.$$

起始值 $r_{-2}=a$ 与 $r_{-1}=b$ 本来就是 $a$ 与 $b$ 的 integer linear combinations。上面的等式通过 induction 说明，每个后续 remainder 也都是 $a$ 与 $b$ 的 integer linear combination。第一个零 remainder 前面的 divisor 等于 $d$，所以反向代入 Euclidean steps 就能把 $d$ 写成 $sa+tb$。

输入中有零的情况可以直接处理。若 $b=0$，则 $d=|a|$：可以取 $s=1,t=0$（当 $a>0$），或取 $s=-1,t=0$（当 $a<0$）。若 $a=0$，可以取 $s=0,t=1$（当 $b>0$），或取 $s=0,t=-1$（当 $b<0$）。两个输入都非零时，对 $|a|$ 与 $|b|$ 使用正整数情形；若原输入为负，再改变对应 coefficient 的符号。这样就证明了所有不同时为零的整数输入。

对前面的较小例子，

$$7=21-14=21-(35-21)=-35+2(21).$$

因此 $35$ 与 $21$ 的一组 Bézout coefficients 是 $s=-1$、$t=2$。

Extended example：$\gcd(515,42)$

先运行 Euclid's algorithm：

$$\begin{aligned} 515&=12(42)+11,\\ 42&=3(11)+9,\\ 11&=1(9)+2,\\ 9&=4(2)+1,\\ 2&=2(1)+0. \end{aligned}$$

最后一个非零 remainder 是 $1$，所以 $\gcd(515,42)=1$。接着进行回代（back-substitution）：

$$\begin{aligned} 1 &=9-4(2)\\ &=9-4(11-9)\\ &=5(9)-4(11)\\ &=5(42-3(11))-4(11)\\ &=5(42)-19(11)\\ &=5(42)-19(515-12(42))\\ &=233(42)-19(515). \end{aligned}$$

因此，

$$\boxed{1=-19(515)+233(42).}$$

这同时验证了 gcd，并给出 Bézout coefficients $s=-19$ 与 $t=233$。