扩展 Euclid 算法

1. 概述

于 初等数论 中, 扩展 Euclid 算法 在 Euclid 算法 计算最大公因数的同时, 求出一组实现 裴蜀恒等式 的整数系数. 它可用于求解 线性 Diophantine 方程 与计算 模逆元.

2. 定义

定义 1 (扩展 Euclid 算法)

设 且 . 对 Euclid 算法 中的余数序列, 令：

并在每一步按商 递推：

当 Euclid 算法输出 时, 同时输出 . 称这一过程为 扩展 Euclid 算法.

3. 例子

例子 2 ( 与 的裴蜀系数)

由：

反向代入得到：

因此 扩展 Euclid 算法 可输出 及一组裴蜀系数 .

4. 相关性质

定理 3 (扩展 Euclid 算法的正确性)

设 且 . 扩展 Euclid 算法 输出的 满足：

证明 4 (扩展 Euclid 算法的正确性)

对每个余数 证明 . 初始等式 与 成立. 若对 成立, 则：

恰与系数递推一致. 因而输出时 ; 再由 Euclid 算法的终止性与正确性, .

5. 相关概念

• Euclid 算法
• 裴蜀恒等式
• 线性 Diophantine 方程
• 模逆元

6. 术语翻译

中文	英文
扩展 Euclid 算法	extended Euclidean algorithm

初等数论