查看“︁扩展 Euclid 算法”︁的源代码

[[分类:整除理论]]
[[分类:数论算法]]
{{InfoBox
|name=扩展欧几里得算法
|eng_name=extended Euclidean algorithm
}}
'''扩展<ins>欧几里得</ins>算法'''是一种算法，在[[辗转相除法|<ins>欧几里得</ins>算法]]计算[[最大公因数]]的算法基础上，利用每步的不完全商计算[[裴蜀定理|<ins>裴蜀</ins>定理]]取得这个最大公因数时的整系数。

== 算法 ==

=== 原理 ===

对整数 <math>a,b</math> ，记 <math>r_0 = |a|, r_1 = |b|</math> ，不断用较大数对较小数取余，并用结果替代较大数，即 <math>r_{k+1} = r_{k-1} - r_{k} q_k</math> 。直到某个 <math>r_{m+1} = 0</math> ，此时较小数 <math>r_m</math> 即是两个数的公约数。

此外，循环时记 <math>s_{k+1} = s_{k-1} - s_{k} q_k, t_{k+1} = s_{k-1} - s_{k} q_k</math> ，则在 <math>r_{m+1}=0</math> 时有 <math>\operatorname{gcd}(a, b) = r_m</math> 的同时，对应的 <math>u = s_m, v = t_m</math> 就满足 <math>\operatorname{gcd}(a, b) = u a + v b</math> 。

=== 伪代码 ===

<syntaxhighlight>
过程 扩展欧几里得算法
别名 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ₖ₋₁
</syntaxhighlight>


{{整除与质数}}