GCD & LCM
Greatest common divisor and least common multiple, with Euclid's steps.
About this calculator
Enter two or more numbers and get both the GCD (also called HCF) and the LCM at once. For a pair, the page shows Euclid's algorithm line by line โ the repeated division that finds the GCD in a handful of steps โ and how the LCM falls out of it via a ร b รท GCD.
What they're each for
The GCD answers "what's the biggest piece that measures both?" โ it's the number you divide by to put a fraction in lowest terms (18/24 รท 6 = 3/4), the largest square tile that fits a floor exactly, the biggest equal team size for two groups. The LCM answers "when do these cycles line up?" โ the common denominator for adding fractions, the day two schedules coincide (every 6 days and every 8 days โ every 24), the meshing point of gear teeth. Euclid's algorithm itself deserves its fame: replace the larger number with the remainder of dividing it by the smaller, repeat, and the last non-zero remainder is the GCD โ 2,300 years old, still literally what your computer executes, and provably near-optimal. The prime-factor view (shared primes โ GCD, all primes at highest power โ LCM) is the other lens: the factorisation tool shows those building blocks.
Frequently asked questions
What's the difference between GCD and HCF?
None โ greatest common divisor and highest common factor are the same thing under two curricula's names. LCM is its counterpart for multiples.
How does Euclid's algorithm work?
Divide the larger number by the smaller and keep the remainder; repeat with the smaller number and that remainder until the remainder is zero. The last non-zero remainder is the GCD โ usually just a few steps even for huge numbers.
How are GCD and LCM related?
For two numbers, GCD ร LCM = a ร b. So once Euclid gives the GCD, the LCM is one division away โ which is exactly how this calculator computes it.
What's the LCM used for in real life?
Common denominators when adding fractions, and any 'when do cycles align?' question โ buses every 12 and 18 minutes leave together every 36; two gear wheels return to their start after LCM-many teeth.