GCD and LCM calculator
The largest number that divides them all, and the smallest number they all divide.
Greatest common divisor (GCD)
Greatest common divisor (GCD): 6
- Least common multiple (LCM)
- 180
Step by step
- 18 = 1 × 12 + 6
- 12 = 2 × 6 + 0
- gcd(12, 18) = 6
How it works
The GCD is found with Euclid’s algorithm: divide the larger number by the smaller, keep the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCD.
The LCM of two numbers is their product divided by their GCD. For more numbers, both are applied one pair at a time. Big integers are used, so very large numbers are exact.
Formula
gcd(a, b) = gcd(b, a mod b), gcd(a, 0) = a lcm(a, b) = |a × b| ÷ gcd(a, b)
Worked example
For 12, 18 and 30: gcd(12, 18) = 6 and gcd(6, 30) = 6, so the GCD is 6. lcm(12, 18) = 36 and lcm(36, 30) = 180, so the LCM is 180.
Questions people ask
Are GCD, GCF and HCF the same?
Yes. Greatest common divisor, greatest common factor and highest common factor are three names for the same number.
What does a GCD of 1 mean?
The numbers are coprime: they share no factor except 1, like 8 and 15.
Where is the LCM used?
To find a common denominator when adding fractions, and to work out when repeating events line up again.