数学统计 · GCD and LCM · 更新于 2026-10-25
最大公约数与最小公倍数是什么：定义、公式与实例
定义
最大公约数（GCD/gcd(a,b)）是同时整除 a 和 b 的最大正整数；最小公倍数（LCM）是同时被 a 和 b 整除的最小正整数。两者由恒等式 gcd(a,b) × lcm(a,b) = a × b 桥接——求其一可得另一。求 GCD 用辗转相除法（欧几里得算法）：gcd(a,b)=gcd(b, a mod b)，迭代到余数为零，效率 O(log min(a,b))，是现存最早（公元前 300 年《几何原本》）且仍在最广泛使用的算法之一。应用：分数约分（约去 GCD）、通分（LCM 做公分母）、排班/发车周期问题（LCM 求重合时刻）、模运算与密码学。
公式
gcd(a,b) = gcd(b, a mod b)；lcm(a,b) = a×b ÷ gcd(a,b)
数值实例
gcd(48, 36)：48 mod 36=12 → gcd(36,12)：36 mod 12=0 → GCD=12。LCM = 48×36÷12 = 144。两路公交分别 48/36 分钟一班，同时发车后再相遇要等 144 分钟。
常见误区
「GCD 一定要枚举所有因子」——辗转相除法几步就收敛，枚举在大数上完全不可行；「lcm 直接 a×b」——那是有公倍数关系的上限值，只有 gcd=1（互质）时才等于最小公倍数。
配套计算器
相关术语
继续探索
浏览完整术语表，或回到首页使用 1435 款免费在线计算器。
返回术语表