Euclid 算法

1. 概述

于 初等数论 中, Euclid 算法 通过反复执行 整数上的带余除法 计算两个正整数的 最大公因数. 它把较大的输入逐步替换为更小的余数, 并在余数变为 时终止.

2. 定义

定义 1 (Euclid 算法)

设 且 . 令 、, 并依次使用 整数上的带余除法 写成：

当首次出现 时停止, 并输出最后一个非零余数 . 称这一过程为 Euclid 算法.

别名 2 (Euclid 算法)

Euclid 算法 亦称为 Euclidean 算法 或 辗转相除法.

3. 例子

例子 3 (计算 )

依次作 整数上的带余除法：

因此 Euclid 算法 输出 , 即 .

4. 相关性质

命题 4 (最大公因数在带余除法下不变)

设 且 . 则：

证明 5 (最大公因数在带余除法下不变)

若 同时整除 , 则 ; 反之, 若 同时整除 , 则 . 因此 与 具有完全相同的 公因数, 从而 最大公因数 相同.

定理 6 (Euclid 算法的终止性与正确性)

设 且 . Euclid 算法 在有限步后终止, 且其输出为 .

证明 7 (Euclid 算法的终止性与正确性)

终止性

算法产生严格递减的非负整数序列 . 这样的序列不可能无限延续, 因而必在有限步后出现余数 .

正确性

由 最大公因数在带余除法下不变, 每一步都有 . 因此：

5. 相关概念

• 扩展 Euclid 算法
• 最大公因数
• 整数上的带余除法

6. 术语翻译

中文	英文
Euclid 算法 / 辗转相除法	Euclidean algorithm

初等数论