Euclidean 算法

阐述

问题

给定正整数 $a,b$，求出 $\gcd(a,b)$，并且找到 $x,y$ 使得 $ax+by=\gcd(a,b)$。

算法

$$\begin{aligned} r_{0} &=a & r_{1}=b \\ s_{0} &=1 & s_{1}=0 \\ t_{0} &=0 & t_{1}=1 \\ & \vdots & \vdots \\ r_{i+1} &=r_{i-1}-q_{i} r_{i} & \text { and } 0 \leq r_{i+1}<\left|r_{i}\right| &\left(\text { this defines } q_{i}\right) \\ s_{i+1} &=s_{i-1}-q_{i} s_{i} & & \\ t_{i+1} &=t_{i-1}-q_{i} t_{i} & & \\ & \vdots & & \end{aligned}$$

当 $r_{k+1}=0$ 时，$r_k$ 即为最大公约数，且 $r_k=as_k+bt_k$。

实例

性质

相关内容

参考文献

• Extended Euclidean algorithm