最大公约数

概述

最大公约数（Greatest Common Divisor, GCD）是同时整除两个整数 $a$ 和 $b$ 的最大整数，记作 $\gcd (a,b)$。当 $\gcd (a,b)=1$ 时，称 $a$ 和 $b$ 互素（relatively prime）。最小公倍数（Least Common Multiple, LCM）是同时被 $a$ 和 $b$ 整除的最小正整数，记作 $\mathrm{lcm}(a,b)$。GCD 和 LCM 满足核心关系 $\gcd (a,b)\cdot \mathrm{lcm}(a,b)=ab$。通过算术基本定理的素因子分解，GCD 取各素因子指数的最小值，LCM 取最大值。

定义

最大公约数（Definition 2）

设 $a$ 和 $b$ 是不全为零的整数。同时整除 $a$ 和 $b$ 的最大整数 $d$ 称为 $a$ 和 $b$ 的最大公约数，记作 $\gcd (a,b)$。

互素与两两互素（Definition 3 & 4）

• $\gcd (a,b)=1$ 时，称 $a$ 和 $b$ 互素（relatively prime）
• 对一组整数 $a_1,a_2,\dots ,a_n$，若对所有 $1\le i<j\le n$ 都有 $\gcd (a_i,a_j)=1$，则称它们两两互素（pairwise relatively prime）
• 注意：两两互素 $\Rightarrow$ 互素，但反之不成立（反例：$\{6,10,15\}$ 的 $\gcd =1$ 但非两两互素）

最小公倍数（Definition 5）

正整数 $a$ 和 $b$ 的最小公倍数是同时被 $a$ 和 $b$ 整除的最小正整数，记作 $\mathrm{lcm}(a,b)$。

素因子分解法求 GCD 和 LCM

设 $a=p_1^{a_1}{p}_2^{a_2}\cdots p_n^{a_n}$，$b=p_1^{b_1}{p}_2^{b_2}\cdots p_n^{b_n}$，则： $\gcd (a,b)=p_1^{\min (a_1,b_1)}{p}_2^{\min (a_2,b_2)}\cdots p_n^{\min (a_n,b_n)}$ $\mathrm{lcm}(a,b)=p_1^{\max (a_1,b_1)}{p}_2^{\max (a_2,b_2)}\cdots p_n^{\max (a_n,b_n)}$

核心性质

性质	描述	说明
GCD-LCM 关系	$\gcd (a,b)\cdot \mathrm{lcm}(a,b)=ab$	Theorem 5，对正整数成立
素因子分解求 GCD	取各素因子指数的 $\min$	依赖于算术基本定理
素因子分解求 LCM	取各素因子指数的 $\max$	依赖于算术基本定理
互素	$\gcd (a,b)=1$	不意味着没有公因子以外的关系
两两互素	任意两个数的 GCD 都为 1	比互素更强的条件
GCD 的对称性	$\gcd (a,b)=\gcd (b,a)$	GCD 是交换的
GCD 与线性组合	$\gcd (a,b)$ 是 $sa+tb$ 中的最小正整数	贝祖定理的推论
$\gcd(a, 0) =	a	$

关系网络

graph TB
    A["最大公约数"] --> B["欧几里得算法"]
    A --> C["贝祖定理"]
    A --> D["整除"]
    A --> E["算术基本定理"]

    A --> F["GCD 定义"]
    A --> G["LCM 定义"]
    A --> H["GCD·LCM = ab"]
    A --> I["互素/两两互素"]

    F --> F1["同时整除 a 和 b 的最大整数"]
    G --> G1["同时被 a 和 b 整除的最小正整数"]
    H --> H1["Theorem 5"]
    I --> I1["gcd(a,b) = 1"]
    I --> I2["两两互素 ⇒ 互素"]

    B --> B1["高效计算 GCD: O(log b)"]
    C --> C1["gcd(a,b) = sa + tb"]
    D --> D1["GCD 基于整除关系定义"]
    E --> E1["素因子分解法求 GCD/LCM"]

    style A fill:#5cb85c,color:#fff
    style B fill:#4a90d9,color:#fff
    style C fill:#d9534f,color:#fff
    style E fill:#e8a838,color:#fff

• 欧几里得算法 通过辗转相除高效计算 GCD，复杂度 $O(\log b)$，无需先分解素因子
• 贝祖定理 揭示了 GCD 的代数本质：$\gcd (a,b)$ 是 $sa+tb$ 中的最小正整数
• 整除 是 GCD 的定义基础：GCD 是同时整除 $a$ 和 $b$ 的最大整数
• 算术基本定理 保证了素因子分解法求 GCD/LCM 的正确性

章节扩展

第4章：数论与密码学

最大公约数是第 4 章 4.3 节的核心概念：

• 4.3 素数与最大公约数：GCD 定义（Definition 2）、LCM 定义（Definition 5）、互素（Definition 3）、两两互素（Definition 4）、GCD-LCM 关系（Theorem 5）、素因子分解法
• 4.3 欧几里得算法：辗转相除法是计算 GCD 的高效方法
• 4.4 解同余方程：线性同余方程 $ax\equiv b(\mathrm{mod}m)$ 有解当且仅当 $\gcd (a,m)\mid b$
• 4.5 密码学应用：RSA 中需要选择与 $\varphi (n)$ 互素的公钥指数 $e$

补充

GCD 的数学本质与计算方法

GCD 不仅是数论的基本概念，更在抽象代数中有深刻推广。在整数环 $\mathbb{Z}$ 中，GCD 的存在性由整环的唯一分解性（即算术基本定理）保证。计算 GCD 有两种主要方法：(1) 素因子分解法：先分解 $a$ 和 $b$ 为素因子乘积，再取各指数的最小值——但素因子分解本身是计算困难的；(2) 欧几里得算法：通过反复带余除法，在 $O(\log b)$ 时间内高效计算 GCD，无需分解素因子。GCD-LCM 关系 $\gcd (a,b)\cdot \mathrm{lcm}(a,b)=ab$ 可以通过素因子分解直接验证：对每个素因子 $p_i$，$\min (a_i,b_i)+\max (a_i,b_i)=a_i+b_i$。

学术来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.). McGraw-Hill, Section 4.3.

参考链接：Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press, Chapter V.

参见

• 欧几里得算法 — 通过辗转相除高效计算 GCD 的经典算法，复杂度 $O(\log b)$
• 贝祖定理 — $\gcd (a,b)=sa+tb$，GCD 的线性组合表示
• 整除 — GCD 的定义基础，基于整除关系
• 算术基本定理 — 素因子分解法求 GCD/LCM 的理论基础