Math & Statistics · 最大公约数与最小公倍数 · Updated 2026-10-25
What Is GCD and LCM?
Definition
GCD is the largest integer dividing both a and b; LCM the smallest multiple of both. They satisfy gcd(a,b)×lcm(a,b)=a×b; the Euclidean algorithm computes GCD in O(log min(a,b)).
Formula
gcd(a,b) = gcd(b, a mod b); lcm = a×b / gcd(a,b)
Worked Example
gcd(48,36)=12, lcm=144 — two buses every 48 and 36 minutes meet again after 144 minutes.
Common Misconception
"GCD requires listing all factors" - the Euclidean algorithm converges in a few steps; listing fails on big numbers. "lcm = a x b" - that is the upper bound when factors are shared; only when gcd = 1 (coprime) does it equal the LCM.
Matching Calculators
Related Terms
Keep Exploring
Browse the full glossary, or head back to the homepage for 1,435 free online calculators.
Back to glossary