GCD 和 LCM 的关系？

对任意正整数 a,b：GCD(a,b)×LCM(a,b)=a×b。先求 GCD（欧几里得算法），再除得 LCM，比直接枚举更快。

欧几里得算法怎么算 GCD？

反复用「大数 mod 小数」替换：GCD(48,18)=GCD(18,12)=GCD(12,6)=GCD(6,0)=6，直到余数为 0，最后的除数即 GCD。

GCD / LCM 计算器 - 最大公约数

← ToolBox / 最大公约数与最小公倍数

📖 查看「GCD / LCM 计算器使用指南」

gcd(a,b) · lcm(a,b) = |a·b|

Compute the greatest common divisor and least common multiple of a set of integers.

📐 计算公式

最大公约数与最小公倍数（本页代码口径）：辗转相除 while(b){t=b; b=a mod b; a=t} 得 g=|a|；lcm=|a×b|÷g。校验：无强校验，a、b 自动四舍五入取整、空值按 0 兜底。判据：两数均为 0 时直接输出 gcd=0、lcm=0；否则恒满足 gcd×lcm=|a×b|。

辗转相除法求最大公约数，再求最小公倍数。

整数 a

整数 b

📌 计算说明

gcd(48,36)=12。
lcm = |ab|/gcd = 144。

📚 深度解析：最大公约数与最小公倍数

💡 常见使用场景

约分分数：分子分母同除以最大公约数 GCD
通分或求周期重合：用最小公倍数 LCM
密码学、数论中判断互质

约分与通分

GCD(12,18)=6，故 12/18 约分为 2/3；LCM(4,6)=12，故 1/4 与 1/6 通分分母为 12。关系：LCM(a,b)=a×b/GCD(a,b)，即 4×6/2=12。

互质判断

GCD(8,15)=1，两数互质；互质时 LCM=两数之积。

❓ 常见问题（FAQ）

GCD 和 LCM 的关系？: 对任意正整数 a,b：GCD(a,b)×LCM(a,b)=a×b。先求 GCD（欧几里得算法），再除得 LCM，比直接枚举更快。
欧几里得算法怎么算 GCD？: 反复用「大数 mod 小数」替换：GCD(48,18)=GCD(18,12)=GCD(12,6)=GCD(6,0)=6，直到余数为 0，最后的除数即 GCD。

Formula & Standard References

Item	Formula / Note	Source / Standard
Euclidean algorithm	gcd(a,b) = gcd(b, a mod b) until the remainder is 0	Euclid, Elements, c. 300 BC
GCD×LCM identity	gcd(a,b) × lcm(a,b) = a × b for two numbers	Standard number-theory identity
Algorithm complexity	Worst case O(log min(a,b)); slowest on consecutive Fibonacci numbers (Lamé)	Lamé's theorem 1844
Extensions	Extended Euclid solves ax+by=gcd for modular inverses and RSA	Number-theory / crypto foundation

📊 结果解读

结果含义

最大公约数(GCD)为两整数公有最大因子；最小公倍数(LCM)为最小公共倍数。满足 GCD(a,b)·LCM(a,b)=|a·b|。

用途

约分、通分、周期对齐、模运算等。常用欧几里得算法（辗转相除）高效求解。

GCD / LCM 计算器