GCD and LCM Calculator
Find the greatest common divisor (GCD) and least common multiple (LCM) of two or more numbers, step by step: the division ladder taught at school, Euclid’s algorithm and prime factors.
- LCM (least common multiple)180
- Coprime?No
Division ladder
How it is calculated
The GCD is the largest number that divides all of them; it simplifies fractions and splits things into equal parts. The LCM is the smallest number all of them divide; it gives a common denominator and answers “when will these coincide again?”. Two numbers with GCD 1 are coprime.
GCD = Π p^(smallest exponent) · LCM = Π p^(largest exponent) · GCD(a, b) × LCM(a, b) = a × bp: a prime factor of at least one of the numbers. The GCD takes only the primes common to all, at their smallest power; the LCM takes every prime at its largest power.- Write the numbers side by side and divide by the smallest prime that divides at least one of them (the others come down unchanged) until all are 1.
- A prime that divides every number in its row is marked “common”.
- The GCD is the product of the common divisors; the LCM, of all of them.
- In Euclid’s algorithm, divide the larger number by the smaller, then the divisor by the remainder; when the remainder is zero, the last divisor is the GCD.
Example
12, 18 and 30: 12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5. The common primes 2 and 3 at their smallest powers give GCD = 6. Every prime at its largest power gives LCM = 2² × 3² × 5 = 180. By Euclid, GCD(48, 18): 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0 → 6; LCM = 48 × 18 ÷ 6 = 144.
Frequently asked questions
How are the GCD and LCM related?
For two numbers, GCD(a, b) × LCM(a, b) = a × b. With GCD(48, 18) = 6, LCM = 48 × 18 ÷ 6 = 144. For three or more numbers this usually fails.
How does the LCM help add fractions?
The LCM of the denominators is the common denominator: for 1/4 + 1/6, LCM(4, 6) = 12, so 3/12 + 2/12 = 5/12. To simplify, divide top and bottom by their GCD.
How do I find the GCD of three or more numbers?
Two at a time: GCD(a, b, c) = GCD(GCD(a, b), c), and the same for the LCM. The division ladder handles all of them at once.
What does coprime mean?
Numbers whose only common divisor is 1 (GCD = 1); they need not be prime themselves. 8 and 15 are coprime, so their LCM is their product, 120.