欧几里得算法

这篇文章主要介绍了：

最大公约数（GCD）与欧几里得算法；
平衡欧几里得算法；
扩展欧几里得算法。

# 1 GCD与欧几里得算法

# 1.1 整除和素数

除法定理 $\forall a,b(a\in\mathbb{Z}\land b\in\mathbb{Z}^*\rightarrow\exists!q,r(q,r\in\mathbb{Z}\land 0\leq r<|b|\land a=bq+r))$ 。其中， $q$ 称为商， $r = (a \operatorname{mod} b)$ 称为余。如果 $r=0$ ，那么我们说 $b$ 整除 $a$ ， $b$ 是 $a$ 的约数，记作 $b|a$ 。

GCD的定义 对 $d\in\mathbf{Z}^*$ ， $a,b\in\mathbf{Z}$ ，若 $d|a\land d|b$ ，则我们成 $d$ 是 $a$ 和 $b$ 的公约数。如果 $d$ 是所有公约数中最大的，就称为最大公约数（GCD），记为 $\mathrm{gcd}(a,b)=d$ 。

注： $\mathrm{gcd}(a,0)$ 一般定义为 $a$ 。

欧几里得定理 $\forall a,b,q,r(q,r\in\mathbb{Z}\land a,b\in\mathbb{Z}^*\land a=bq+r\rightarrow\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r))$ 。

证明：

$\begin{aligned} &\mathrm{gcd}(a,b)|a-bq=r\Rightarrow\mathrm{gcd}(a,b)|\mathrm{gcd}(b,r) \\ &\mathrm{gcd}(b,r)|a=bq+r\Rightarrow\mathrm{gcd}(b,r)|\mathrm{gcd}(a,b) \end{aligned}$

# 1.2 欧几里得算法的实现

gcd(a, b) =

# 1.3 欧几里得算法的复杂性估计

引理： $\forall a,b(a,b\in\mathbb{Z}\land0<b\leq a\rightarrow a\operatorname{mod}b\leq \frac{a-1}{2})$ 。分 $b\leq\frac{a}{2}$ 和 $b>\frac{a}{2}$ 两种情况讨论即可证明。

定理欧几里得算法复杂度上界：

$\forall a,b(a,b\in\mathbb{Z}^+\rightarrow\mathrm{gcd}(a,b)\text{的带余除法运算次数}\leq\lfloor 2\log_2\max\{a,b\}\rfloor+1)$

证明方法是构造数列 $r_i (i=-1,0,\cdots)$ ，其中：

$\begin{cases} r_{-1} = a \\ r_0 = b \\ r_{i+1} = r_{i-1}\operatorname{mod}r_i &(i \geq 0) \end{cases}$

由此 $r_{j+1}\leq\frac{r_{j-1}-1}{2}$ 。注意它是隔一个元素减半，这就到之类复杂度上界多了系数 $2$ 。

# 1.4 二进制欧几里得算法

$\mathrm{gcd}(0,v)=v$ ；
如果 $u,v$ 都是偶数， $\mathrm{gcd}(u,v)=2\mathrm{gcd}(u/2,v/2)$ ；
如果 $u$ 是偶数， $v$ 是奇数， $\mathrm{gcd}(u,v)=\mathrm{gcd}(u/2,v)$ ；
如果 $u$ 是奇数， $v$ 是偶数， $\mathrm{gcd}(u,v)=\mathrm{gcd}(v/2,u)$ ；
如果 $u,v$ 都是奇数且 $u\geq v$ ， $\mathrm{gcd}(u,v)=\mathrm{gcd}((u-v)/2, v)$ 。

# 2 平衡的欧几里得算法

第1泛化除法定理 $\forall a,b,d(a,d\in\mathbb{Z}\land b\in\mathbb{Z}^*\rightarrow\exists!Q,R(Q,R\in\mathbb{Z}\land d\leq R<|b|+d\land a=bQ+R))$ 。特别地，令 $d=-|\frac{m}{2}|$ ，则 $-|\frac{m}{2}|\leq R<|\frac{m}{2}|$

第1泛化欧几里得定理 $\forall a,b,q,r(q,r\in\mathbb{Z}\land a,b\in\mathbb{Z}^*\land a=bq+r\rightarrow\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)=\mathrm{gcd}(b,-r)=\mathrm{gcd}(b,b-r))$ 。

定理第1泛化欧几里得算法复杂度上界：

$\forall a,b(a,b\in\mathbb{Z}^+\rightarrow\mathrm{gcd}(a,b)\text{的带余除法运算次数}\leq\lfloor\log_2\max\{a,b\}\rfloor+1)$

注：系数2不见了，时间复杂度在常数上有了进步。主要来源于构造的数列不再是隔一个减半，而是相邻减半： $r_{j}\leq\frac{r_{j-1}-1}{2}$ 。

# 3 扩展欧几里得算法

# 3.1 Bézout等式

Bézout等式：

$\forall a,b(a,b\in\mathbb{Z}\rightarrow\exists u,v(u,v\in\mathbb{Z}\land\mathrm{gcd}(a,b)=ua+vb))$

证：定义 $S=\{au+bv\mid u,v\in\mathbb{Z}\}$ ，我们要证明 $\forall n(n\in S\leftrightarrow\mathrm{gcd}(a,b)|n)$ 。“ $\rightarrow$ ”比较简单，我们要证明“ $\leftarrow$ ”。

引理1： $\forall x,y(x,y\in S\rightarrow x\pm y\in S)$ 。易证。
引理2： $\forall x,c(x\in S\land c\in\mathbb{Z}\rightarrow cx\in S)$ 。易证。由两引理知 $S$ 元素的整数线性组合仍属于 $S$ 。
引理3： $S = \{kd|d=\min S\cap\mathbb{Z}^+, k\in\mathbb{Z}\}$

$\begin{aligned} &\text{左$\supseteq$右：由引理2易知}\\ &\text{左$\subseteq$右：}\begin{aligned}[t] &x\in S,\text{令}x=qd+r (0\leq r<d)\text{为除法定律分解}\\ \Rightarrow&r = x - qd \in S\land r<d\\ \Rightarrow&r=0\\ \Rightarrow&d|x \end{aligned} \end{aligned}$
令 $d=\min S\cap\mathbb{Z},D=\mathrm{gcd}(a,b)$ ，则 $d=D$ 。证，可以知道 $D|a\land D|b\Rightarrow D|d$ 。又有引理3， $a\in S\land b\in S\Rightarrow d|a\land d|b\Rightarrow d|D$ 。得证。

# 3.2 扩展欧几里得算法的实现

gcd(a, b) =

# 3.3 欧几里得算法的矩阵诠释

对于普通的欧几里得算法，给定初始 $a_0,b_0$ ，我们可以递推：

$[a_i, b_i]=[a_{i-1},b_{i-1}]\begin{bmatrix} 0 & 1 \\ 1 & -\lfloor\frac{a_{i-1}}{b_{i-1}}\rfloor \end{bmatrix},(i\geq 1)$

当 $b_i = 0$ ， $a_i=\mathrm{gcd}(a_0, b_0)$ 。

对于扩展欧几里得算法，我们可以采用如下的递推：

$\begin{cases} \begin{bmatrix} u_0 & e_0 \\ v_0 & f_0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\\ \begin{bmatrix} u_i & e_i \\ v_i & f_i \\ a_i & b_i \end{bmatrix} = \begin{bmatrix} u_{i-1} & e_{i-1} \\ v_{i-1} & f_{i-1} \\ a_{i-1} & b_{i-1} \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & -\lfloor\frac{a_{i-1}}{b_{i-1}}\rfloor \end{bmatrix}, &(i\geq 1) \end{cases}$

当 $b_i = 0$ ， $a_i=\mathrm{gcd}(a_0, b_0)=u_ia_0+v_ib_0$ 。