GCD and LCM Calculator
The greatest common divisor (GCD) and least common multiple (LCM) are two of the most useful results in number theory. The GCD reduces fractions and ratios to lowest terms; the LCM finds common denominators and works out when repeating cycles align. This calculator finds both for two whole numbers using the Euclidean algorithm, then derives the LCM from the identity that the GCD times the LCM equals the product of the two numbers. Enter two integers to see both results.
GCD and LCM formula
GCD: Euclidean algorithm, repeat g = GCD(b, a mod b) until remainder 0
LCM = (a * b) / GCD(a, b)
The Euclidean algorithm finds the GCD without factorising. The LCM follows directly because the product of the GCD and the LCM always equals the product of the two numbers.
Worked example
For 12 and 18: the Euclidean algorithm gives 18 mod 12 = 6, then 12 mod 6 = 0, so the GCD is 6. The LCM is (12 times 18) / 6 = 216 / 6 = 36. So GCD(12, 18) = 6 and LCM(12, 18) = 36.
GCD and LCM: frequently asked questions
What is the greatest common divisor (GCD)?
The greatest common divisor of two integers is the largest positive integer that divides both without a remainder. For example, the GCD of 12 and 18 is 6. The GCD is found efficiently with the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of dividing it by the smaller until the remainder is zero.
What is the least common multiple (LCM)?
The least common multiple of two integers is the smallest positive integer that is a multiple of both. For example, the LCM of 4 and 6 is 12. The LCM is most easily computed from the GCD using the identity LCM(a, b) = (a times b) divided by GCD(a, b), which avoids listing multiples.
How are GCD and LCM related?
For any two positive integers, the product of the GCD and the LCM equals the product of the two numbers: GCD(a, b) times LCM(a, b) = a times b. This relationship lets you compute one from the other. It is why this calculator finds the GCD first with the Euclidean algorithm and then derives the LCM by dividing the product by the GCD.
Where are GCD and LCM used in practice?
The GCD is used to reduce fractions and ratios to lowest terms. The LCM is used to find common denominators when adding fractions, and to work out when repeating events coincide, such as two buses leaving every 4 and 6 minutes meeting again after 12 minutes. Both appear throughout number theory, scheduling and gear-ratio problems.
Official sources
- National Institute of Standards and Technology: NIST Digital Library of Mathematical Functions.
- National Institute of Standards and Technology: NIST mathematics and statistics.
Reviewed by the CalculatorHub team, edited by James Graham, 19 June 2026. See our methodology.