GCD & LCM calculator
Greatest common divisor and least common multiple, with the Euclidean steps.
Separate with commas or spaces — two or more
Prime factorisations
| Number | Prime factors |
|---|---|
| 12 | 2^2 × 3 |
| 18 | 2 × 3^2 |
| 24 | 2^3 × 3 |
The GCD takes the lowest power of each shared prime; the LCM takes the highest power of every prime that appears.
How it works
The greatest common divisor is the largest number that divides all of your inputs exactly. The least common multiple is the smallest number they all divide into. They are two views of the same prime factorisations.
gcd(a, b) × lcm(a, b) = a × b Euclid's algorithm
Replace the larger number with the remainder of dividing it by the smaller, and repeat. When the remainder reaches zero, the last divisor is the answer. It is over two thousand years old and still the method every computer uses, because it takes a handful of steps even for enormous numbers.
What each one is for
- GCD
- Simplifying fractions (divide top and bottom by it), cutting material into equal pieces with no waste, finding the largest tile that fits a floor exactly.
- LCM
- Adding fractions (it is the least common denominator), and any “when do these two cycles line up again?” question — buses, gears, planetary orbits.
Coprime numbers
When the GCD is 1, the numbers share no factors and are called coprime. Their LCM is simply their product. This is the condition RSA key generation depends on, and the reason gear teeth counts are often chosen to be coprime — it spreads wear evenly instead of mating the same two teeth forever.