Euclidean Algorithm

定义 Definition

欧几里得算法：一种用于求两个整数最大公约数（GCD）的经典方法。核心思想是反复用“较大数 ÷ 较小数取余”，直到余数为 0，此时最后一个非零余数就是最大公约数。（也常用于多项式的最大公因式等场景。）

发音 Pronunciation

/juːˈklɪdiən ˈælɡəˌrɪðəm/

例句 Examples

The Euclidean algorithm finds the greatest common divisor of two numbers.
欧几里得算法用于求两个数的最大公约数。

In cryptography, we often rely on the Euclidean algorithm to compute inverses modulo a number, which helps make RSA work efficiently.
在密码学中，我们常用欧几里得算法来计算模逆元，从而使 RSA 等方法能够高效运行。

词源 Etymology

“Euclidean” 源自古希腊数学家欧几里得（Euclid）之名；该算法在古代数学著作《几何原本》（Elements）中就已出现并被系统化记录。“algorithm” 一词则源于中世纪对波斯学者 al-Khwārizmī（花剌子密）姓名的拉丁化形式，后来泛指“计算步骤/算法”。合起来，“Euclidean algorithm” 就是“欧几里得提出/记载的求最大公约数的方法”。

相关词 Related Words

• Algorithm
• Greatest Common Divisor
• Divisor
• Remainder
• Modular Arithmetic
• Coprime
• Extended Euclidean Algorithm

文学与经典作品 Literary Works

• Euclid, _Elements_（《几何原本》）：以早期形式呈现并讨论了用辗转相除法求“公度量/最大公约数”的思想。
• G. H. Hardy & E. M. Wright, _An Introduction to the Theory of Numbers_（《数论导引》）：在基础数论中系统讲解最大公约数与欧几里得算法。
• Donald E. Knuth, _The Art of Computer Programming_（《计算机程序设计艺术》）：以算法分析视角讨论包括欧几里得算法在内的经典算法与效率。