GCD and LCM Calculator

What are the GCD and the LCM?

The GCD (greatest common divisor) is the largest number that divides all the given numbers. The LCM (least common multiple) is the smallest positive number that all of them divide. You use the GCD to reduce fractions and the LCM to find a common denominator. This tool finds both for two to six numbers and shows three separate methods step by step.

The Euclidean algorithm

Divide the larger number by the smaller one and keep the remainder. Then divide the smaller number by that remainder. Repeat until the remainder is zero. The last divisor is the GCD. For 1071 and 462: 1071 = 462 · 2 + 147, 462 = 147 · 3 + 21, 147 = 21 · 7 + 0, so the GCD is 21. This method needs no factoring and stays fast for very large numbers.

The prime factor method

Each number is split into prime factors. The GCD takes the smallest exponent of every shared prime and the LCM takes the largest exponent of every prime. For 48 = 2⁴ · 3 and 18 = 2 · 3² that gives GCD = 2 · 3 = 6 and LCM = 2⁴ · 3² = 144.

The division ladder

This is the layout taught at school. Write the numbers side by side and divide by primes, smallest first. Mark a prime when it divides every number in the row. The product of the marked primes is the GCD and the product of all the primes is the LCM.

Check and limits

For two numbers GCD · LCM = a · b always holds: 6 · 144 = 864 = 48 · 18. For three or more numbers it usually does not. The tool works with non-zero whole numbers only. Decimals and fractions are not accepted and negative numbers are replaced by their absolute values.