LCM vs GCD
LCM vs GCD compared — least common multiple vs greatest common divisor, formulas and uses, with a free calculator.
The GCD (greatest common divisor) is the largest number that divides two values; the LCM (least common multiple) is the smallest number both divide into. They are linked: LCM(a,b) × GCD(a,b) = a × b.
LCM vs GCD at a glance
| LCM | GCD | |
|---|---|---|
| Meaning | Smallest common multiple | Largest common divisor |
| Always | ≥ both numbers | ≤ both numbers |
| Used for | Adding fractions, cycles | Simplifying fractions |
When to use LCM
Use the LCM to find a common denominator or when two cycles re-align.
When to use GCD
Use the GCD to simplify a fraction or split into equal groups.
Tools for LCM & GCD
LCM vs GCD
什么是欧几里得算法？
一种求两个整数最大公约数（GCD）的方法：不断用较大数除以较小数所得的余数替换较大数，直到余数为 0 为止。
欧几里得算法的时间复杂度是多少？
O(log min(a, b))——运算步数与数字的位数成正比，这正是它即使面对非常大的数字也能极快求解的原因。
为什么 gcd(a, b) = gcd(b, a mod b)？
a 和 b 的任何公约数也必然能整除 a mod b（反之亦然），因此这种替换不会改变公约数的集合——自然也就不会改变最大公约数。
GCD 有哪些用途？
用于约分分数、模运算、扩展欧几里得算法（模逆元、RSA 加密），以及通过公式 lcm(a,b) = a·b / gcd(a,b) 计算最小公倍数。