扩展 Euclid 算法

扩展欧几里得算法
术语名称	扩展欧几里得算法
英语名称	extended Euclidean algorithm

扩展欧几里得算法是一种算法，在欧几里得算法计算最大公因数的算法基础上，利用每步的不完全商计算裴蜀定理取得这个最大公因数时的整系数。

算法

原理

对整数 [math]\displaystyle{ a,b }[/math] ，记 [math]\displaystyle{ r_0 = |a|, r_1 = |b| }[/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} = s_{k-1} - s_{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ₖ₋₁

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解