How it works
The greatest common divisor (GCD, also called the greatest common factor or HCF) is computed with Euclid’s algorithm: replace the larger number by the remainder of dividing it by the smaller one until the remainder is 0. For more than two numbers the step is repeated pairwise.
The least common multiple (LCM) follows from the GCD: lcm(a, b) = |a × b| ÷ gcd(a, b), again applied pairwise. All arithmetic uses exact integers, so even 30-digit numbers give exact results.
Euclid’s algorithm, step by step
Example for 1071 and 462: each line divides the previous divisor by the remainder, and the last non-zero remainder is the GCD.
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0 → gcd = 21
gcd(a, b) = gcd(b, a mod b) · lcm(a, b) = |a × b| ÷ gcd(a, b)
Where you need it
- GCD: reduce a fraction, e.g. 18/24 becomes 3/4 after dividing by gcd 6.
- LCM: find a common denominator, or when repeating events line up again (every 4 and every 6 days → every 12 days).
- GCD: cut tiles, rows or groups into equal parts with nothing left over.
Tips
- Two numbers are coprime when their GCD is 1; they can still both be composite, like 8 and 9.
- gcd(a, b) × lcm(a, b) = a × b for two positive numbers, a handy check.
- Zero is allowed: gcd(a, 0) = a, but any LCM involving 0 is 0.
Standards and sources
- Euclid’s algorithm · NIST Dictionary of Algorithms and Data Structures
- Least common multiple · NIST Dictionary of Algorithms and Data Structures
Last reviewed October 20, 2026
Frequently asked questions
What is the difference between GCD and LCM?
The GCD is the largest number that divides all the numbers; the LCM is the smallest number that all of them divide. For 12 and 18 the GCD is 6 and the LCM is 36.
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.
How many numbers can I enter?
As many as you like; the GCD and LCM are worked out pairwise. Prime factors are listed for the first 12 numbers.