GCD and LCM Calculator
The greatest common divisor of two numbers is the largest value that divides both without a remainder.
The GCD of 12 and 18 is 6: it divides both, and no larger number does.
When the GCD is 1, the numbers are called coprime — they share no divisor other than 1, even if neither is prime on its own. That is the case for 8 and 9.
The calculation uses the method Euclid described more than two thousand years ago, and it remains the most efficient for the general case.
The idea is simple: 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 GCD.
For 48 and 18: 48 divided by 18 leaves remainder 12; 18 by 12 leaves 6; 12 by 6 leaves 0. The GCD is 6.
Its efficiency is remarkable — the number of steps grows logarithmically, so even enormous numbers resolve in few iterations. That is why this tool works with arbitrary-precision integers, with no practical size limit.
- Simplifying fractions: divide numerator and denominator by the GCD and the fraction reaches lowest terms in one step.
- Dividing an area into equal squares of the largest possible size.
- Splitting quantities into equal groups with nothing left over.
- Public key cryptography, where checking that numbers are coprime is a fundamental step.
The least common multiple of two numbers is the smallest value that both divide without a remainder.
The LCM of 4 and 6 is 12: the first number appearing in both times tables.
It is never smaller than the larger of the two numbers, and at most equals their product — which happens exactly when they are coprime.
LCM and GCD are two sides of the same calculation. The product of the two numbers always equals the product of their LCM and GCD.
That means you only need the GCD from Euclid’s algorithm and then divide the product by it — which is how this tool finds the LCM without factorising anything.
For 4 and 6: the product is 24, the GCD is 2, so the LCM is 12. The relationship holds for any pair.
A practical consequence: the larger the GCD, the smaller the LCM. Numbers sharing many divisors have a low common multiple.
- Adding fractions with different denominators: the LCM of the denominators is the common denominator.
- Finding when two periodic events coincide — buses every 12 and 18 minutes coincide again every 36.
- Synchronising gears and maintenance cycles with different intervals.
- Planning rotas and shift rotations that must repeat in phase.
Frequently asked questions
That the numbers are coprime: they share no divisor other than 1. Neither needs to be prime on its own — 8 and 9 have a GCD of 1.
Divide numerator and denominator by their GCD. For 18 over 24 the GCD is 6, and the simplified fraction is 3 over 4.
Yes. The sign is dropped before the calculation, because divisibility does not depend on it. The GCD is always positive.
Not in practice. The calculation uses arbitrary-precision integers, and Euclid’s algorithm resolves enormous numbers in few iterations.
The GCD is the largest number dividing both; the LCM is the smallest that both divide. The GCD is never larger than the smaller number, and the LCM never smaller than the larger one.
When they are coprime, that is, when the GCD is 1. For 8 and 9 the LCM is 72, exactly their product.
Find the LCM of the denominators and convert both fractions to that common denominator before adding the numerators.
Not in practice. The calculation uses arbitrary-precision integers, so very large numbers lose no precision.