GCD & LCM Calculator
Calculate the greatest common divisor (GCD) and least common multiple (LCM) of two numbers.
How the Euclidean algorithm finds GCD
This calculator uses the Euclidean algorithm, an efficient ancient method for finding the greatest common divisor: repeatedly replace the larger number with the remainder of dividing it by the smaller number, until the remainder is zero — the last nonzero remainder is the GCD.
This method is dramatically faster than checking every possible divisor, especially for large numbers, and remains one of the oldest algorithms still in common use today, dating back over 2,000 years.
The relationship between GCD and LCM
GCD and LCM are connected by a simple formula: GCD(a,b) × LCM(a,b) = a × b. This means once you know the GCD, finding the LCM is straightforward division rather than a separate calculation.
LCM is commonly used when adding fractions with different denominators (finding the smallest common denominator) and in scheduling problems, like determining when two repeating events will next align.
Frequently asked questions
What's the difference between GCD and LCM?
GCD (greatest common divisor) is the largest number that divides both numbers evenly. LCM (least common multiple) is the smallest number that both numbers divide into evenly — they answer opposite kinds of questions.
Where is LCM used in everyday math?
LCM is most commonly used to find a common denominator when adding or comparing fractions, and in scheduling problems involving repeating cycles or events.