首页 > 生活 >

欧几里得算法

发布时间:2026-05-14 15:53:47来源:

【欧几里得算法】欧几里得算法,又称辗转相除法,是求两个正整数的最大公约数(GCD)的一种经典方法。该算法由古希腊数学家欧几里得在其著作《几何原本》中提出,至今仍被广泛应用于数论、密码学和计算机科学等领域。

该算法的核心思想是:对于两个正整数 $ a $ 和 $ b $(假设 $ a > b $),若 $ a $ 能被 $ b $ 整除,则 $ b $ 就是它们的最大公约数;否则,用 $ a $ 除以 $ b $ 得到余数,再用 $ b $ 和这个余数继续进行同样的操作,直到余数为零为止,此时的除数即为最大公约数。

欧几里得算法步骤总结

步骤 操作 说明
1 输入两个正整数 $ a $ 和 $ b $ 例如:$ a = 48 $, $ b = 18 $
2 若 $ b = 0 $,则返回 $ a $ 如果 $ b = 0 $,说明 $ a $ 是最大公约数
3 计算 $ a \mod b $,得到余数 $ r $ 例如:$ 48 \mod 18 = 12 $
4 将 $ a $ 替换为 $ b $,将 $ b $ 替换为 $ r $ 现在 $ a = 18 $, $ b = 12 $
5 重复步骤 2-4,直到 $ b = 0 $ 最终得到最大公约数

示例演示

以 $ a = 48 $, $ b = 18 $ 为例:

运算步骤 值 说明
1 $ a = 48 $, $ b = 18 $ 初始值
2 $ 48 \mod 18 = 12 $ 余数为 12
3 $ a = 18 $, $ b = 12 $ 更新值
4 $ 18 \mod 12 = 6 $ 余数为 6
5 $ a = 12 $, $ b = 6 $ 更新值
6 $ 12 \mod 6 = 0 $ 余数为 0
7 $ b = 0 $,结束 最大公约数为 6

优点与应用

特点 说明
高效性 算法复杂度为 $ O(\log n) $,效率高
简单易实现 只需基本的取余操作即可完成
应用广泛 用于求最大公约数、分数约分、密码学中的模逆元计算等

总结

欧几里得算法是一种简洁而高效的求解最大公约数的方法,其原理基于“余数递减”的思想,通过不断迭代缩小问题规模,最终得出结果。该算法不仅在数学中具有重要意义,也在现代信息技术中发挥着重要作用。