Greatest Common Divisor

释义 Definition

最大公因数（简称 GCD）：两个（或多个）整数都能被整除的公因数中最大的那个。若两个数的最大公因数为 1，则称它们互质。该概念也常用于分数约分与数论、算法中。（在某些语境下也称 greatest common factor，但数学与计算机领域更常用 greatest common divisor。）

发音 Pronunciation (IPA)

/ˌɡreɪtɪst ˌkɑːmən dɪˈvaɪzər/

例句 Examples

The greatest common divisor of 12 and 18 is 6.
12 和 18 的最大公因数是 6。

To simplify the fraction, divide the numerator and denominator by their greatest common divisor.
要化简分数，把分子和分母同时除以它们的最大公因数。

词源 Etymology

Greatest common divisor 由三部分组成：greatest（最大的）+ common（共同的）+ divisor（除数/因子）。其中 divisor 源自拉丁语 dīvidere（“分开、划分”）。这一思想在古希腊数学中已很成熟，欧几里得算法（《几何原本》）就是求最大公因数的经典方法之一。

相关词 Related Words

• Divisor
• Factor
• Multiple
• Prime
• Coprime
• Euclidean Algorithm
• Least Common Multiple
• Modular Arithmetic

文学与经典著作 Notable Works

• Euclid, Elements（《几何原本》：以“最大公度/公因数”的思想与欧几里得算法奠定基础）
• G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers（《数论导引》：使用并讨论 greatest common divisor）
• Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics（《具体数学》：在数论与算法章节中频繁出现）
• Donald E. Knuth, The Art of Computer Programming（《计算机程序设计艺术》：用 GCD 作为算法与证明的常见例子）