最大公因数

1. 概述

于 初等数论 中, 最大公因数 是能够被所有公因数整除的正公因数. 对正整数按整除关系构成的 偏序集 而言, 两个元素的最大公因数正是它们的 交.

2. 定义

定义 1 (最大公因数)

设 , 且它们不全为 . 称 为 的 最大公因数, 当：

1. 是 的 公因数;
2. 对任意公因数 , 都有 .

记号 2 (最大公因数)

的 最大公因数 记为 . 特别地, 两个整数 的最大公因数记为 .

注记 3 (全零情形)

通常约定 .

3. 例子

例子 4 (初步例子)

• , 因为 是二者的公因数, 且每个公因数都整除 ;
• ;
• .

例子 5 ( 与 的裴蜀表示)

因为 , 且：

所以 与 是一组裴蜀系数.

4. 相关性质

命题 6 (最大公因数的存在性)

任意不全为 的有限个 整数 都存在 最大公因数.

证明 7 (最大公因数的存在性)

继承自 裴蜀恒等式.

命题 8 (最大公因数的基本性质)

对任意 ：

1. 若 不同时为 , 则 最大公因数 唯一;
2. ;
3. ;
4. 若 , 则 .

证明 9 (最大公因数的基本性质)

1. 若 都是 最大公因数, 则 且 . 由 整除的基本性质 的 (6), 有 ; 又 , 故 .
2. 与 具有相同的公因数, 因而最大公因数相同.
3. 一个整数整除 当且仅当它整除 , 对 同理, 因而两组公因数相同.
4. 同时整除 与 ; 任意公因数 都整除 , 从而整除 .
   

定理 10 (裴蜀恒等式)

设 , 且它们不全为 . 则 存在, 并且存在 使：

此外, 是这些整数线性组合中的最小正整数.

证明 11 (裴蜀恒等式)

令：

并令 . 因 不全为 , 某个 或 属于 , 故 非空. 由 良序原理, 存在最小元 , 且按 的定义可写成 .

对每个 , 由 整数上的带余除法, 可写 , 其中 . 因 , 有 . 若 , 则 且 , 与 的最小性矛盾. 因而 , 即 .

若 是 的任意 公因数, 则由 公因数与整数线性组合, 整除 . 因此 满足 最大公因数 的两个条件, 并且它已由构造成为最小正整数线性组合.

推论 12 (最大公因数为 的线性组合判据)

设 , . 则 当且仅当存在 使：

证明 13 (最大公因数为 的线性组合判据)

充分性 ( )

若 最大公因数 为 , 所需线性组合直接由 裴蜀恒等式 得到.

必要性 ( )

若存在等于 的整数线性组合, 则任意公因数都整除 . 正的最大公因数因而只能是 .

定理 14 (Euclid 引理的一般形式)

设 , 且 . 若 , 则 .

证明 15 (Euclid 引理的一般形式)

由 裴蜀恒等式, 存在 使 . 两侧乘以 得：

因 , 且由假设 可得 , 故由 整除的基本性质 的 (4), 有 .

5. 相关概念

• 公因数
• 最小公倍数
• 互素
• 两两互素
• Euclid 算法
• 扩展 Euclid 算法
• 线性 Diophantine 方程
• 素数
• 交

6. 术语翻译

中文	英文
最大公因数	greatest common divisor
裴蜀恒等式	Bézout’s identity
Euclid 引理	Euclid’s lemma

初等数论