GCD & LCM Calculator

The greatest common divisor (GCD) is the largest natural number that divides both numbers, and the least common multiple (LCM) is the smallest of their common multiples. They are essential for reducing fractions and finding common denominators.

This calculator quickly finds the GCD and LCM of two natural numbers using the Euclidean algorithm. Useful for reducing fractions to lowest terms or finding a common denominator.

For example, the GCD of 12 and 18 is 6, and the LCM is 36.

GCD & LCM Calculator Calculation Method

Greatest common divisor (GCD): 0

Least common multiple (LCM): 0

About This Calculator

The greatest common divisor (GCD) is the largest number that divides two integers exactly, and the least common multiple (LCM) is the smallest number both divide into. GCD simplifies fractions; LCM finds common denominators and synchronises repeating cycles.

Enter two natural numbers to get their GCD and LCM, with the Euclidean algorithm steps shown.

GCD and LCM are tied together by gcd(a, b) × lcm(a, b) = a × b, so computing one gives the other. For 84 and 126 the GCD is 42 and the LCM 252, and indeed 42 × 252 = 10,584 = 84 × 126. The Euclidean algorithm reaches the answer in a handful of divisions even for enormous numbers.

Key Formula:GCD(a, b) via Euclid: gcd(a, b) = gcd(b, a mod b) · LCM(a, b) = a × b / GCD(a, b)

Frequently Asked Questions

What is the Euclidean algorithm?

A 2,300-year-old method that repeatedly replaces the larger number with the remainder of dividing it by the smaller until the remainder is zero; the last non-zero remainder is the GCD. It is fast even for very large numbers.

When do I need the LCM?

Whenever events repeat on different cycles or fractions need a common denominator. If one bus comes every 12 minutes and another every 18, they coincide every LCM(12, 18) = 36 minutes.

How does the Euclidean algorithm work?

Replace the larger number by the remainder of dividing it by the smaller and repeat until the remainder is zero. For 84 and 126: 126 mod 84 = 42, then 84 mod 42 = 0, so the GCD is 42.

Where is the LCM useful in practice?

Adding fractions, scheduling repeating events and aligning gear teeth. For cycles of 12 and 15 minutes the LCM of 60 minutes gives the first coincidence after exactly one hour.

Related Calculators

Sources & last update

2026-10-19