扩展 Euclid 算法
| 扩展欧几里得算法 | |
|---|---|
| 术语名称 | 扩展欧几里得算法 |
| 英语名称 | extended Euclidean algorithm |
扩展 Euclid 算法是 Euclid 算法的扩展，在其计算最大公因数的基础上，利用每步的不完全商计算 Bézout 定理取得这个最大公因数时的整系数，即 Bézout 系数。
算法
原理
对整数 [math]\displaystyle{ a,b }[/math] ，记 [math]\displaystyle{ r_0 = a, r_1 = b }[/math] ，不妨设 [math]\displaystyle{ |r_0|\geq |r_1| }[/math] （如果不满足这一条件，算法中的第一个循环中会自动交换两数的位置顺序，为简便叙述不做特殊说明），不断用较大数对较小数取余，并用结果替代较大数，即 [math]\displaystyle{ r_{k+1} = r_{k-1} - r_{k} q_k }[/math] 。直到某个 [math]\displaystyle{ r_{m+1} = 0 }[/math] ，此时较小数 [math]\displaystyle{ r_m }[/math] 即是两个数的公约数。
此外，循环时记 [math]\displaystyle{ s_{k+1} = s_{k-1} - s_{k} q_k, t_{k+1} = t_{k-1} - t_{k} q_k }[/math] ，则在 [math]\displaystyle{ r_{m+1}=0 }[/math] 时有 [math]\displaystyle{ \operatorname{gcd}(a, b) = r_m }[/math] 的同时，对应的 [math]\displaystyle{ u = s_m, v = t_m }[/math] 就满足 [math]\displaystyle{ \operatorname{gcd}(a, b) = u a + v b }[/math] 。
伪代码
过程 扩展欧几里得算法
别名 extended_euclidean_algorithm
参数 a, b : 整数 // 被求最大公因数的两个数
返回 : 自然数, 整数, 整数 // 最大公因数，整系数
令 r₀ ← a, s₀ ← 1, t₀ ← 0
令 r₁ ← b, s₁ ← 0, t₁ ← 1
循环 k ← 1
当 rₖ ≠ 0 时
执行
记 qₖ, rₖ₊₁ ← rₖ₋₁ divmod rₖ
记 sₖ₊₁ ← sₖ₋₁ - qₖ sₖ
记 tₖ₊₁ ← tₖ₋₁ - qₖ tₖ
继续循环 k ← k + 1
返回 rₖ₋₁, sₖ₋₁, tₖ₋₁