LCM & GCD Calculator (Least Common Multiple, Greatest Common Divisor)
Calculate the GCD (greatest common divisor) and LCM (least common multiple) of any list of integers using Euclid's algorithm.
What this calculates
GCD (greatest common divisor, or GCF — greatest common factor) is the largest integer that divides all the numbers evenly. LCM (least common multiple) is the smallest integer that all the numbers divide evenly into. Used in fraction math, scheduling, cycle alignment, and cryptography. This calculator handles any list of integers.
Formula & how it works
Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), recursively until b = 0. lcm(a, b) = a × b ÷ gcd(a, b). For multiple numbers: fold across the list — gcd(a, b, c) = gcd(gcd(a, b), c). Time complexity O(log min(a, b)) per pair — fast even for huge numbers.
Worked example
Numbers: 12, 18, 24. GCD = gcd(12, 18) = 6, then gcd(6, 24) = 6. LCM = lcm(12, 18) = 36, then lcm(36, 24) = 72. Verification: 12 = 6×2, 18 = 6×3, 24 = 6×4 (GCD divides all). 72 ÷ 12 = 6, 72 ÷ 18 = 4, 72 ÷ 24 = 3 (LCM is divisible by all).
Frequently asked questions
Why GCD and LCM matter?
Simplifying fractions (divide numerator and denominator by GCD). Finding common denominators (use LCM). Scheduling repeating events. Music (rhythm cycles). Cryptography (RSA key generation uses GCD as a primality check).
What if all numbers are coprime?
GCD = 1 (numbers share no common factor). LCM = product of all. Common in cryptography — prime numbers used in RSA are coprime to each other.
Difference between GCF and GCD?
Same thing. GCF (greatest common factor) is more common in US K-12 education. GCD (greatest common divisor) is more common in math and programming.
Largest number this works for?
JavaScript handles integers up to 2^53 (about 9 quadrillion). For RSA-scale (hundreds of digits), use BigInt — same algorithm but with arbitrary precision.